All the contacts that have, at one point in time, been on your contact list, have to be fall in either the 'allowed' list or 'blocked' list. Stupid as that may seem, that's how it works.
You can't delete contacts out of either one of those categories. You can delete contacts off your lists, but not out of those two catergories, like I already just mentioned.
Final conclusion: Once a contact adds you, or once you add a contact, there's no way to really get rid of him. You can delete them from your list, but not out of either one of the categories, so for all added contacts, you either allow them to see you (even if they're not on your list, unless you check off 'Only people on my Allow list can see my status and send me messages') or, you have them blocked using the blocking feature.
Secondly, deleting the MSN preferences will not change anything, other than reset your MSN preferences that you personally set for your copy of MSN Messenger -- the information is stored on the server in regards to your contacts and contact list.
MacBook Pro (15-inch, Mid 2012) 2.3 GHz Core i7, 8GB, 256GB SSD + 500GB HDD + 1TB FW800 OWC Mercury Elite Pro mini
iPhone 4S • iPod nano 8GB • Sound System Audio Engine A2 • Display UltraSharp U2412M 24"