This seems to be a behavior that has existed in the ArcGIS Server Silverlight API since time immemorial, or at least since we've been using it. It has persisted through multiple new releases, and appears impervious to logical solutions. For the longest time, an Esri search on the topic would suggest you make sure:
1. Your server is running;
2. Your service is running;
3. Your URL is correctly formed.
and that's all that would be said. Off-the-record, you hear "Oh yeah, it does that." Well that's helpful.
Since a simple refresh typically would eliminate the problem, it kind of excludes any of the "is your computer plugged in" suggestions given.
Newer releases (3.2) seem less plagued by it, but it sitll pops up, as you say, randomly. We've tried pretty much everything anyone has suggested, short of goats bones and chicken blood.
The only thing that seems to make a significant difference is setting the time that the service refreshes (set by default to midnight) to various other times, so that not all services are trying to refresh simultaneously at 12:00am.
That has worked for us, about 97% of the time.
Moving to the JSAPI at this point looks like the best option, even though that means scuttling any past development work using the SLAPI. HTH.