I am right there with you bud I just had the same issue today. I formatted my drive completely forgetting I never paid for lion it came on my Mac. Well I try to install from the cloud and it tells me I didn't purchase it of course.
That really doesn't make sense. The computer doesn't come with physical media or Internet recovery. I believe you. It just doesn't make sense.
I recently got a MacBook Pro back from repair and while it originally came with Mountain Lion, the OS X Internet Recovery system only lets me download Lion. So I had to pay to upgrade to what the computer originally had.
Droidrage729's case is with a used mini that originally had Tiger or perhaps Leopard. Swingerofbirch's case probably is with a system that originally had Lion but perhaps qualified for the free upgrade. Was this also a used system?
Prior to Lion systems came with recovery disks. I understand that these disks are available from Apple for a small fee. Early systems that came with Lion (and all later systems) have a recovery partition that will download the system via the Internet and a program is available that will copy the recovery partition to a USB flash drive so you are covered in case of a drive failure or replacement as long as you make the recovery drive first! New systems that were released after Lion came out have the ability to restore the OS directly from the Internet (Apple calls this "OS X Internet Recovery"). OS X Internet Recovery restores the OS that was originally on the system.
Systems that have been upgraded to Lion or Mountain Lion via the Mac App Store have non-transferable licenses, so that if the system is sold they cannot (legally) be sold with the upgraded OSes. Such systems should be restored to their original OS either by the recovery disks (save those disks!), a saved Lion Recovery flash drive, or via OS X Internet Recovery. The gotcha here is that a Lion system that didn't have OS X Internet Recovery once it is upgraded to Mountain Lion has no way to go back unless the recovery USB flash drive was made.
On the purchaser end, it is certainly "buyer beware" and the safest bet is to only buy a used system with Snow Leopard or earlier recovery disks provided, or one that is running the same OS that was on the system when purchased (might be tricky to determine!).
In any case, nothing beats buying an external hard drive and cloning your internal drive for later recovery. It's fast and sure, if not cheap.