2009 + Creative extensions comes with ProOptimize (formerly
a plug-in called polycruncher) which preserves UV's. The creative extensions where free to those on subscription. It was rolled into later releases of 3dsmax also. Polycruncher wasn't free but I think there was a trial available.
I'd give my left nut for an optimizer that works on visible edges and quads rather than at the triangle level...