My n900 has also has had intermittent problems with skype "Message Sending Failed" and it is an intermittent problem.

I just reset my skype on my phone by:
1. Turning Off Skype
2. Deleting My Skype Account
3. Removing Skype files in terminal with:
mv .Skype .Skype.YYYY-MM-DD
4 Resetting up my skype account

I have done this in the past when skype wasn't working at all so I hope to not get the "Message Sending Failed" message again.

Not sure how the skype setup gets corrupted in the first place.
- Power Issues? (Lithium Ion Batteries are only good for 2-3 years)
- Bad internet connection?
- Bad software?