Steve,
If there is no network icon in the status bar, then yes, I suppose it could have something to do with that....
One thing to check is the "master kill switch" for background sync in the device's system settings, under accounts and sync.
As for deleting messages, are you moving to the deleted folder? Is it set to sync with the server's deleted folder (there should be a color indicator on the left of the [ Deleted] folder item in the account list, unless you've disabled them all).
Could you try selecting a test message in one of these accounts' message lists, then doing Menu / Delete now, finally checking web mail (if you have access to it), to see if it worked? Just a test?