QUOTE
came with 10.7 installed and only a small "base system" on the restore partition
That's the way it comes on all new machines. That's why there is no "install media" (except for a ~$70 USB drive option that wasn't even available when the OS was released). Even if those machines were running Snow Leopard when Lion was installed (via a purchase from the App Store), they
still would not have any "install media." The "install media" is the (hidden) partition that the installer puts on the "media" already in the machine.
The normal way to Restore the OS is to, uhmn...use the Restore option, hold down the "r" key on a Startup. I would
definitely not attempt to download the OS from the App Store. Since the OS was not purchased or downloaded there, it will
never give you an option to "RE"-download. That is only allowed when you had bought it there in the first place.
I'm not sure why any Firewall is in the equation, every install has its own (hidden) Restore partition. There's no need for any network connection, that I'm aware of.
What most people did, after discovering that there is no "install media" available (short of spending another 70 bucks!) is to "Restore" the OS to a thumb drive of their own. I forget the exact steps now, but they are readily available with a web search. Basically, what you want is the original "Installer app" that the OS automatically deletes when it is finished with the instal needs. I believe this "Installer app" is the first thing the Restore function actually does. That "Installer App" then reads the files in the Restore partition (as needed) to complete the Restore/Install and then deletes itself. However, if the installation is on a different drive (the internal or external hard drive, for example) the "Installer App" is not on that drive and cannot, therefore be deleted from it...'cause it ain't there!
Note, most of the above description is my simplified opinion, not from my reading (much less writing) of any Apple Documentation. Those documents, of course, would be my suggested source for the real facts...