The client can setup (i think in outlook) to download mail from the server and to NOT delete it.
Yip it is setup like that , I am 2nd in charge and it is very informal here so no policies etc.

It was just one of the workers whom shift deleted a folder in outlook with all the stored emails. What a tit.

Anyhow system restore didn't work - can someone explain this to me?

http://www.officerecovery.com/freeundelete/

and / or

The free undelete recovered all the files deleted on the OS which was cool but didnt help on the mail side.