Unless you have the option to Leave a copy of messages on server checked in the email account properties (Tools, Accounts, select email account, Properties, Advanced tab), then you are out of luck.
If you do have it checked, then click on the Send/Recieve button to download them again.
Thanks for the prompt reply Shawn,
Since I posted the query I have found a company selling a recovery program for Windows mail.
I have tried the free demo which will find deleted messages and contacts but not do anything with them until you pay ( only $39.95 ).
It will only find them if you run it ASAP after you delete them, I had left it too long and Vista had overwritten them.
I think it will work OK if you do it straight after you have done the delete.