So...
I've tried all 3 plugins.
It seems that both Butterfly and Pecan bring back my deleted contacts, so ironically Haze is the only one that works correctly for me.

However, there are a couple of issues... After trying out all of them multiple times and messing around a little bit, the most annoying issue is that there is no single "MSN" in the Contacts app... all of them are treated separately, and if I try to use for example the entry set up in Haze with Pecan, it gives me the choice, but... for some reason sometimes it makes multiple entries for a single contact, which is quite annoying. This also happens when I install Pecan, log in. I select a contact who has an "MSN (Haze)" entry, and Pecan happily converts it to "MSN (Pecan)". Then I notice that despite Haze has done so already, Pecan also downloads all my contacts and duplicates them. So I merge some of them, and the result for the aforementioned contact, is that it has 2 "MSN (Pecan)" and 1 "MSN (Haze)", entries, all of which containing redundant data.
Add to that, that I also tried out Butterfly. My Contacts app was quite a mess after all this.

I cleaned it up and uninstalled every other one.

Now I have only the "Pidgin protocols plugin for Conversations and Contacts", and the "MSN (Haze)" within works at least.

I've read the linked blog post from FelipeC, saying that Pecan is less buggy and stuff, but still, it brings back my long-deleted contacts, and Haze doesn't. (This means that it adds approx. 100 unnecessary contacts to my already screwed enough contact list.)

Yes, after all this I was thinking about deleting my current MSN account and starting a fresh one, but I couldn't... :P