Factory reset for MBA 2011
I actually called Apple Support and they told me that it is not legal to sell an OSX version purchased in the app store.

The technically correct solution is indeed to (after backing up your data, unlinking the iTunes account and removing the mac from "find my mac" service) wipe the start volume ("Macintosh HD") and to do an internet recovery by pressing CMD+ALT+R on boot.

The error I encountered apparently was because of maintenance work on Apple's servers -- apparently sunday is not a good day to rely on them.

I was able to restore Lion on my MacBook without having to enter my apple id.

BTW: Internet recovery works, but is really slow, so be prepared for that.