Why do apps legitimately purchased from Android Market warn about missing license?
This does sound like Google has messed up your account.  One thing I would try: Uninstall the apps in question, clear the data for the Market, then go into the Market again and re-install them.