Sounds very annoying. There's been
many cases of people having blocked and deleting someone, yet they're still able to talk to them. Even I
experienced the same problem in 2007.
Can you just double-check that, in Tools > Options > Privacy, the contact is definitely in the 'Block list' and that you have 'Only people on my Allow list can see my status and send me messages'.
You may want to contact the Windows Live team personally and they may be able to look into it. If it gets really bad then I'd suggest changing to a new email address.