I haven't tried to do this since 2.49, but I think I used some PolyReduce script or similar. I would hope that Decimate would give better results, but it does know exactly how to remove polygons properly, and it can give some strange results. I thought I remembered there being a retopo tool, too. The best way, I think, is that when creating subdivisions is to use the Multires modifier and only apply it when needed or finished modeling. This way use can easily change the resolution of a mesh.

It is better to do one thing well, than to do many things and excel at nothing.