Licensing is not an issue.
First off, all Mac Minis would have shipped with Tiger pre-installed (thus fully licensed).
As far as Apple's licensing scheme, there are no product keys or installation media id checks to determine how many copies are capable of being installed.
They trust that you will do the right thing.
What I would recommend is powering up in Target Disk Mode (hold the T key at boot up), plug the mini in over firewire to another mac. Open Disk Utility, select the hard disk on the remote computer, format it, restart the other mac, insert your installation disk, try to install.
If this does not work, then you may want to reset your OpenFirmware on that system.
If that still does not work, then you may want to go back to Target Disk Mode, install over firewire onto the problematic mini, connect to Software Update and check to see if there were any firmware updates.
Again, this is all if you do not want to take it into an Apple store where they will most likely resolve this problem same day in front of you for no charge (usually a direct swap for something like this where there is no important data or reason why you would need to keep that physical hardware).