Mail.App deleted, how do I restore it (It's not anywhere accessible on restore media)
The official word from Apple on this is that you need to reinstall the OS.


  If I remove one of the bundled
  applications, such as Safari or Mail,
  how can I get them back?
  You must
  reinstall Mac OS X from the MacBook
  Air Software Reinstall Drive to
  restore bundled applications. To bring
  your computer up to date, use Software
  Update after Mac OS X finishes
  installing.


Another Mac - Before reinstalling the OS, I'd check with a friend that has a Mac and see if you can copy the app from another Mac.

Reinstall to Another Drive - Rather than reinstalling the OS to your  main MacBook Air drive, you could try reinstalling to another drive (e.g. external USB drive). Then you could simply copy the app to your main MacBook Air drive.

Standard Reinstall - If you have to reinstall the OS over your current system, it isn't as painful as on Windows if that is what you are used to. You can keep your user accounts and settings so it may not be too painful.