I bought a brand new tank when I switched to kegging so I refuse to do the exchange thing. I don't purge my keg before filling. I siphon my beer into it, seal it up, and then purge the O2/air out, replacing it with CO2. Is this not acceptable?
I've been looking at other variables for probably a couple years now... :\
Your beer is coming into contact with oxygen, then. Though it's not for a long time, it's still being introduced into the environment - try purging. Once the keg is clean and sanitized, seal it and hit it with 10-15 lbs, release the relief valve a couple of times, then de pressurize, remove the lid and fill her up. Try a few like that and see if it helps.
Also, what pressure do you keep them under for serving? You can over carb which will change some of the flavor profile.