Been awhile since I used Mail and I'm not using a Mac at the moment so will let others deal with retrieval issue. Obviously the more you use the computer the less chance there is to salvage.
As to Telus backing up. Almost certainly, but getting them to help you out here may be next to impossible.
Have you tried accessing your account through webmail (www.teleus.net>webmail) to see if some of the incoming messages are there? Your sent messages were stored in Mail of course.