What that message doesn't say is that licenses can be "bound" to multiple front-end computers. Basically, when we load a page, we check the machine name and SID and see if that machine name is licensed. If it isn't you get a message. You can license multiple machines to the same install so as to do load balancing (so long as they're all pointed at the same database).
If there are old rows, don't worry about them. If they really bother you, go through the diagnostics. The Licenses step has a link to allow you to delete all rows from that table.