My son's 90 Maxima had all those sysmtoms and he tried everything to fix it. The water pump had a small amount of shaft play, so we finally replaced it. When I pulled it off it had NO FINS; completely eroded off. The new pump completely eliminated overheating, puking thru the recovery line, lack off heater function, being hard to purge air from cooling system, etc, etc.
A quick test for this is to warm up the engine and then rev it up while pinching off the radiator hose from the water pump.. If the fins are good you will feel a powerful surge.