Internet recovery is nice but it is not quite as reliable as having an offline recovery. My macbook air 2011 for some reason similar to some other MBA 2011 and mac mini 2011 are unable to reinstall Lion from Internet Recovery.
One solution that I have is to clone a fresh install of Lion to an external drive (i.e. USB drive, SD card). To avoid having to download the Base System from the Apple servers and save time, I have also created a bootable Base System (look for BaseSytem.dmg (note: show hidden files) within the InstallESD.dmg). The Base System will also allow me to boot the Macbook air into recovery mode and access Disk Utility which I can use to clone/restore the Lion image from an external drive. I have not timed the total time it took me to restore to my macbook air but I would think that it would be faster than having to download Lion + install.
@idroid84, are you able to send me the InstallESD.dmg for a macbook air 2011 and I can take a look on how to create an offline recovery tool? From my discussion with the AppleCare support, I don't think Apple will create/provide an offline recovery tool going forward. I would send again another feedback via the link you provided but it could take some time before we see results. I rely on my macbook at work and at home thus I don't want to sit around waiting for Apple to make a move.