Not directly by using some button or feature.
However, you _could_ find it out in some ways... First to know is that Messenger uses several lists: you have a "contact list", an "allow list", a "block list" and a "reverse list". It is by comparing those to eachother you could find out:
1) First of all, if you have your contact list exported at one point, you could try to import it back in...
2) Second, with the use of Messenger:
If you use Windows Live Messenger, you are in luck as deleted contacts (if they are also in your associated hotmail contact list) will show up as "non-instant messaging contacts" in your contact list (sort by groups to easly see them).
Otherwise, go to
Tools > Options > Privacy. There you'll see a button called "View", press that. The next screen will tell you all the people who have added you.
If you compare that list manually (yeah I know it's a bitch) with your contact list, you can find out the people who have you on their list but you don't have them on your list.
3) You can also do this by comparing your "allow list" with your "contact list"
4) If you also have blocked the contact, you can look in the "block list" instead.
5) As an almost last method and provided you didn't blocked the contact, you could also allow everybody to contact you. In this way, the deleted contact could start chatting with you, and you would notice/remember instantly (hopefully) if she/he isn't added to your list. All this requires is patience and disabling the option:
Tools > Options > Privacy > "Only people on my allow list can see my status"
EDIT: 6) With the use of a 3rd party tool (much more convenient than to use Messenger for this):
Download and execute
NoRoom's List Manager. With this program you can manipulate your various lists more easly. Compare the lists like described above in previous points.
/ 
