Resolved Help - How to do a clean install of Mountain Lion on Mountain Lion

After booting with command-r did you use Disk Utility to erase the drive before running the Mac OS installer?

An other way is to make a Mountain Lion Installer on a USB drive and use Disk Utility on that to Erase the internal drive prior to installation of the OS.

If your Air is new enough and came with Mountain Lion Installed originally, restoring it will work with command-r even on an erased/empty SSD. (You need to have an internet connection when you do that - Internet Restore)

You should also be able to (re)download ML without paying using your Apple ID if you paid for it originally and the restore partition can be created on an external drive using Recovery Disk Assistant:
http://support.apple.com/kb/DL1433

No problem. I understand that.

If you want to be absolutely sure you can check whether or not your particular MB Air supports this recovery method by posting the question in the Air subsection of the forum but as far as I know this should work as long as you have an internet connection and everything goes as designed.
http://www.apple.com/osx/recovery/

Since you are completely erasing everything I'm assuming you have back-ups of your files.

Start with cmd-r
Use Disk Utility to erase the SSD
Exit Disk Utility
Install OS (Check that you still have an internet connection at this point - a clean System will be downloaded from Apple directly at this point)

You should only have to restart after this installation

If you want to erase the entire SSD including the recovery partition you need to start up from an external drive - which you can prepare to become the startup volume from which you initialise the re-installation of a clean OS as well.