On XP:
Sign out of Messenger. Click Start, then Run, type:
%userprofile%\local settings\application data\microsoft\windows live contacts
and click OK. Right-click the e-mail folder corresponding to your email, and choose Delete. Then sign back into Messenger.
On Vista:
Sign out of Messenger. Click Start, type:
%appdata%\..local\application data\microsoft\windows live contacts
and click OK. Right-click the e-mail folder corresponding to your email, and choose Delete. Then sign back into Messenger.
EDIT: Damn you sunshine