Why do apps legitimately purchased from Android Market warn about missing license? A few weeks ago I purchased two paid apps, 3G Watchdog Pro (3GWP) and The Photographer's Ephemeris (TPE). Both of them displayed warnings that the license is missing, and advised to visit Android Market for purchasing the product. 3GWP issues the warning at startup and won't start unless I buy the app. TPE does start, but issues the warning occasionally.

I had actually bought 3GWP a few months earlier but soon uninstalled it, then decided to install it again a few weeks ago. I purchased the app again after the developer, whom I had contacted, refunded the previous purchase for troubleshooting. He said that refunding/repurchasing usually fixes the issue, and had no other suggestions.

I thought this issue was app-specific, then it occurred with a different app, TPE. I posted a query to the Google Mobile help Forum and was contacted by the TPE developer. He did some troubleshooting, i.e. checked the aLogcat output and whitelisted my account. But the problem persisted.

Today I launched the Wolfram Alpha paid app, which I hadn't used in a while, and it displayed the warning "Application Not Licensed - This Wolfram | Alpha app has not been licensed. Please login to the phone using correct credentials or purchase it from the Android Market", and didn't start.

Why do unrelated, legitimately purchased apps report licensing issues? I suspect the problem is at Google's end.

I have a Nexus S phone with Android 2.3.6. My mobile carrier is Vodafone IT.
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.