I had thought that anything off the App Store was then available for all Macs linked to that account, but when I go to get Lion on my second machine, it asks me to buy it again. Huh?
Did you check under the "purchased" tab in the store.
So you have to redownload it each time? That sounds highly inefficient.