Joe, thanks. LIbrary, message, actually they are all there in Users library, only thing is you have to open many folders to find it..scroll back through time..
In this case, in turned out I found my contact otherwise... but this is the best way for searching for future deleted messages...right?
Sadly I don't think Spotlight can find them...I think you have to manually open all old folders.
