[gss036]

5000 would be at the low end of the WOT rpms. Top end should be somewhere around 5400/5500. I run a 14 1/2 X 17 stainless Merc prop (some cup) and get around 5400 top end on my 89 200 Merc. I don't think you would be lugging at 5000. You say you are overheating at 4000, what temperature are you considering overheating (degrees)? I cruise at 42/4300 for 15-18 miles w/o any rise in temp. Idleing you might get up to 180, but once you are over 2300/2500, the poppet valve should open and cool back down and stay there.
The 1st thing I would check are the thermostats, maybe even change them as they are only about $10 each. They should open at 143 degrees, if not you could be restricting the water flow. The 2nd thing would be the poppet valve assy. Do you have a water pressure guage? If so what is your idle/WOT pressure? That would be a good indicator of the impeller. My Merc factory manual says mine should 12 psi, but engine models differ.
Are EFI or carbed?