To everyone having these problems I very strongly urge you all to report this to Microsoft:
http://support.live.com/eform.aspx?productKey=wlmessenger
Write an as detailed as possible report.
eg: provide a very detailed step by step in what you did before. eg: did you used the handwriting feature before you send a message? What was your status prior to the error. How many texts were send succesfully to your knowledge, what firewall and brand of firewall do you exactly have? Have you ever installed 3rd party software related to messenger (eg: smileycentral, sweet im), How many chat windows are open at the time you tried to send the message, What is the screen name of the contact you're trying to send text too, etc, etc...
Reason for this is that we (Windows Live Messenger MVPs) talked about this particular bug to Microsoft, but they can not pinpoint the problem and even are extremely puzzled at what the cause might be. They NEED your reports to solve this.
I also suggest you all enable the Custom Experience Improvement Program:
Tools > Options > General > Quality Improvement > Allow MS to collect anonymous info
PS, do not mention Messenger Plus!. Messenger Plus! has got nothing todo with this and if you mention Messenger Plus! they probably say it is caused by that. So to cut the chase and get stuff moving a bit faster don't mention you have Plus! installed.
In fact, make 500% sure it isn't Plus! by completely uninstalling it first.
And make sure you did not patched Messenger in any way. So first try to re-install Messenger so you are sure it is a clean copy.
As a final note, note that this problem does have different causes. Some of the causes are legit and very normal. It is possible that you indeed can not send messages. So remember that not all of these "cannot send message" errors are because of a bug (or bugs)!
/ 
