IIRC, the instakill with Counterspy only happens IF the scout is detected, and then the Counterspy shot actually HITS the scout before it recloaks. And the counterspy only has 1 shot every 2 seconds or so, so it's not really all that dangerous.
Also, and I posted on Mantis, but I often don't even unlock mk2 scouts unless I'm having real problems scouting certain areas (this even applies to 120 planet maps with lots of connections, like Realistic/Hubs). I rarely end up unlocking mk3, and I've never needed (or even used) mk4.
I don't think mk3 scouts themselves need a nerf given that you're supposed to be able to scout most of the map with them (otherwise what's the point?), but if there are going to be changes, here's some suggestions:
1. Reverse the ship-cap progression. Most ships lose ship cap as mk level goes up, but scouts are opposite, where you get very few mk1 scouts and a lot of mk3 scouts. If you were given a lot of mk1 scouts (maybe make the progression 20/15/10 instead of 10/20/30), and remove cloaking booster from mk1 scouts to make deep scouting with them much more difficult (so they end up being planetary sentries for the most part).
2. Scouts suffer from attrition outside supply like transports, with varying percentages. Mk1 suffer highest attrition, maybe the same 35% as transports, mk2 down to 20%, and mk3 down to 10%. Mk4 does not suffer. That gives each of the marks set ranges for how far they actually can go, and makes long-range scouting (with a reach of most of the galaxy) still possible with mk3 scouts, but makes it more difficult since they also die easier the farther out they get.