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 M4 SSD
iPhone 6 - 64GB S/G • Sound System Audio Engine A2 • Display UltraSharp U2412M 24"
Custom Built Gaming PC Skylake Edition | 16GB DDR4 | GTX 1070 8G