A couple more suggestions on the MED post-processing...

Firstly, dont try to reduce to your target low-poly-count in a SINGLE step.
Reduce it in 'clean round' stages. Like 50% or 10% steps until you get close
to your target, then start using the odd percentages.

When all is done, if it still looks 'iffy', try using the MED tool "Object/Recalculate Normals".
But try it in the engine first... it may make things look worse...