You've done everything you should to fix it...
Have you cleared data for the Market app in Applications>Manage? If not, try doing that and rebooting and try again.
Doubt that will help after all the other data wipes you've done, but can't hurt, and easy to try.
Did you format /system when you re-installed? No way to know if that's related at all, but that's the only step you don't specifically mention in the standard set of "fix-it" steps you followed.
Have you cleared data for the Market app in Applications>Manage? If not, try doing that and rebooting and try again.
Doubt that will help after all the other data wipes you've done, but can't hurt, and easy to try.
Did you format /system when you re-installed? No way to know if that's related at all, but that's the only step you don't specifically mention in the standard set of "fix-it" steps you followed.
