Those days are over.
Not even the "epic" MBPs are shipping with recovery media any more (and they're not even capable of Internet Recovery if the hdd is wiped/replaced, like the new Airs and minis are).
Give it time. As with the backlight keyboard. Give it time.
As for the restore media I'm really tired of some of you making excuses for Apple.
I should not have to do Apple's job. How is it even remotely acceptable to sell a computer without a 100% viable way to restore it REGARDLESS OF INTERNET CONNECTION? Don't give me the cost BS. As I said, it costs them literally pennies to manufacture.
The beauty of it all is that I'm the furthest thing from an "Apple hater". I gave the Air a fair chance. Love the 4GB RAM, love the processor, love the backlight. Unfortunately I expect everything else to be simply amazing, and it wasn't.
Now maybe if Apple in its infinite wisdom allowed users to downgrade to Snow Leopard, it might be a different experience. Since some of you keep making excuses for clearly hardware issues and blaming it on the software, in theory Snow Leopard should work like gold. But then Apple doesn't want you doing that even though it's capable of such. That's my problem and that's the primary reason it's going back: I won't be keeping a machine where I'm forced to use software that is negatively affecting my experience. That's perfectly reasonable.
If what you say is true and Lion's the problem, don't defend it: it's half-baked, not ready. That means that the various threads blasting Lion aren't too far off base.
Down the road, IF they fix a lot of the issues and it turns out to have been Lion, then I'll reconsider it. Until then it's a $1300+ investment that doesn't have solid returns.