If a reboot is fixing the problem, the most likely scenario is that an intermittent network problem is causing the RUS to hang in an LDAP query. You can determine if this is the case by closely watching the logging and looking for the 8011 and the corresponding 8012's (see Part 2, which was posted today).
The way I typically troubleshoot this is I start a netmon capture with the filter set to Exchange <-> DC, and then cycle the System Attendant. Then I just let the netmon run. Periodically, we'll create a test user and see if he gets stamped. As soon as we notice the RUS is no longer stamping, we stop the netmon capture. Then, I use the app log to see when it last queried against the domain (looking for the 8011 and 8012s), and zero in on that time in the netmon. In the netmon you can follow the TCP conversation and see why it hung.
In one recent case I worked on, this was due to the switch that the DC and the Exchange server were plugged into. We would see a bizarre series of frames where Exchange was acknowledging a particular packet and the DC kept retransmitting an older packet, causing the TCP conversation to fall apart. We changed the switch from autodetect to 100 full duplex, our TCP problems were gone, and the RUS was happy.
It should not be necessary to reboot regularly to keep your RUS working. I'm not familiar with your particular case, but it sounds like your issue can certainly be resolved. I would encourage you to reopen the case with PSS and ask for further analysis of the problem. Point them to this blog or tell 'em to shoot me an email. :-)