Unfortunetly 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/ Reg Editing any thing that may lead to the dissapearance of this data?
Generally Data does not just go missing unless it is corrupt or a bad HD sector or some sort of failure (other than the obvious human removal tactics) although I may be wrong but I haven't experienced it any ways.
However one good thing about windows is it's back-up tape is usually good with things like this that ones uses all the time or is a windows software entity.
... hm at this point I just noted 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 refuring 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 forgoten in the back-up tape; when ever I've had to use this feature I've always done it this way not sure if there is annother way to search the back-up tape other than this.
Sorry can't be much help!