Unfortunately Windows Restore does not do a very good job at all and is not intended as a "System Back-up". It would be nice to know some more information regarding your problem such as, have you done any cleaning, installing, removing, moving, of programs or settings, or Registry editing that may have lead to the disappearance of this data?
Generally data does not just go missing unless it is corrupt or a hard drive sector has gone bad or some other sort of failure has occurred (other than the obvious human removal tactics). I may be wrong but I haven't experienced it anyways.
However one good thing about Windows is its backup tape is usually good with things like this that one uses all the time or is a Windows software entity.
I just realized you are speaking of Windows Live Mail. I was thinking the Windows Calendar but I will try to help.
By Windows Live Mail I believe you are referring to Hotmail and the Passport system which most of the information I believe is stored on their server in which case you may have to contact them. However, if the new Live Mail works like Outlook or you mean Outlook then there is a good chance that info is stored both on your system and on the server.
You could just do a search. This is an acceptable method of searching for items forgotten in the backup tape. Whenever I've had to use this feature I've always done it this way. I'm not sure if there is another way to search the back-up tape other than this.
Sorry can't be much help!