AlexBRFC, did this problem start when you block&delete those contacts? Or just suddenly without you did anything?
If when you deleted&blocked them, then you can untick the Messenger option (Options>Privacy) "Warn me when others add me to their contact lists". this will add them to Allow list automatically when you signin but at least it will prevent Messenger's "contact added you" windows from popping-up.
Also you can give a try to NoRoom's List Manager program:
http://noroom.msnfanatic.com/listmanager/
When you block all of those contacts when Messenger prompt to seect an action for them, sign-in on List Manager and see if block statuses for those contacts have been properly saved at the server side. Then try again the same thing after allowing all of them via Messenger. Because maybe your block list exceeded its limit.
Also with this program, you can delete every contact from all of your Contact list, Allow list and Block list and empty them completely. I am not sure if it helps in any way but it is worth to a try in order not to lose your current account completely.
You can also send emails to those contacts and nicely request them to delete you from their lists.
/ 
