“..should never change the number of verticies of the .obj in any way.”

 Very true,but you can subdivide the mesh by going up a level or two.
That gives you a very dense mesh with a lot of surface to work on.
Then drop it back down to level one (the original poly count) for export.

Note: If you do any smoothing of the mesh, wait until you bring it back down to the original count (level one), or you will get things messed up.