Use ROM Toolbox, select the app in question, scroll on the bottom of the screen over to "break market link".
Works for me every time. The only other thing I'll add is that I have both the Market Feedback Agent & the Market Updater both frozen.
If you've already tried breaking the link, with TiBu or something similar to RTB, I would still give RTB a shot, but if it's still not working go into the settings, applications, system apps, & clear both the cache & the data for the Market itself, then load it back up. I can't imagine why it would still be showing as purchased.