Well looks like I finally talked to someone with some insight and wisdom at RIM!!!
She checked over everything we could think of. Finding nothing obvious we decided to look at the actual tables of the database on the remote SQL server. BINGO! There were table errors in the "SyncServerState" which look like it was causing the handhelds to lose the Desktop(CMIME) which caused the "No Message Service Configured" error or it required the device to be reactivation.
Removed all the corrupted tables. Resent Service books. All looks like it working again. Just hope it stays that way.