This may be a problem with the advertising interval. By default, the RALUS agent only advertises once every 60 minutes. If the media server is restarted after the last advertisement cycle, it will not see the agent again until a new advertisement is sent.
To change the default value, stop the agent, and edit the file
/etc/VRTSralus/ralus.cfg
the line you're looking for is
Software\VERITAS\Backup Exec\Engine\Agents\Advertising Interval Minutes=60
Change the value 60 to a smaller interval (say 5 minutes), start the agent, and see if that corrects the behavior.