For the love of... I have one question for the Gentoo maintainers: "Why?!?!"
Alright my friend, here's the deal. I went to the Gentoo website to pull up their documentation. This is just my opinion, but they needlessly overcomplicated the booting process, and that's going to make it tough for you to figure out what exactly is going on.
I'm sure you already know this, but halting the system pulls its scripts from /etc/runlevels/shutdown. Rebooting pulls its scripts from /etc/runlevels/reboot. That's about as easy as it's going to get.
You'll need to pull out a pen and paper or open a text editor for the next part. The scripts in those directories will be executed in alphabetical order. As you saw though, each script can have dependencies. So what you need to do is map out the sequence of what gets called from start to finish for both halt and reboot. That's going to be a pain in the arse because dependencies may have dependencies, etc. If, for example, you looked at the script for sendmail, it might a dependency on the dhcp script. So the sequence would be dhcp->sendmail, but you'll have to examine dhcp to see if it has dependencies (like network). So the full sequence would be network->dhcp->sendmail.
Anyway, once you've contructed the list, compare the shutdown and reboot sequences. Look at the stop() portion of the scripts called after urandom in the halt sequence. Your problem is going to be there. You'll have to manually check each one. If there's a command to display text in one of them, you know the problem is happening between the end of urandom and the display attempt. Focus your attention there. If you look at the scripts and need some help, post them, and I'll do my best to help out.
EDIT:
I don't have a man page for rc-update, but it might help figure out the order. The documentation refers to using
to show all scripts and which runlevels execute them. There may be an option to specify what the sequence is for a specific runlevel. Check your man page to see.