Me (maybe).
Try this one:
instead deleting and making an MSN account again simply delete all contacts (don't be afraid, you won't lose 'em) then make a connect.
It should connect and give again all your contacts back.
It is still an annoiance but not the same as go into preferences.
I also disabled the "ask me before deleting contact", what we should need would be to remove the "go online to remove contact" or at least it should appear only once for a multipe deletion.
Developers are you reading this??
(if so keep up the good work)
Bye
