The groups is understandable..wether to show those or not is set in the registry. You will need to remove the group on the other computer aswell.
Asfor contacts returning that's something different, your contactlist is stored on MSN servers. Try to delete this contact again and if you see it return again contact Microsoft support at
http://feedback.live.com
P.S. Msg Plus! does not infere in any of this...both things are MSN features.