the 99 - 08 generation was Yamaha powerhead on a Mercury leg and cooling problems are notorious. There's a rubber grommet between the waterways on the powerhead and the leg. A mismatch of Yamaha and Mercury metals causes electrolytic corrosion which in turn closes the rubber grommet up and restricts the waterway or closes it up altogether - cheap in parts to fix, expensive in labour or your own DIY time.
But before pulling the powerhead (it's probably already been done once or twice on a 15 year old engine), worth checking the impeller is OK.