Usually if it works at speed it is an airflow issue. Above about 25mph or so, more air is being forced in then most fans will ever be able to pull, that's why a pusher fan usually is less efficient, it blocks the natural airflow making it to the radiator when you start moving. OEMs use pullers for that reason. If it got better with the pusher, could the pusher fan be rated for much higher cfm than the original puller was? That may explain why it helped some, not the fact that it is pushing the air, but the fact that it is moving more air than before.
Could also be a thermostat issue.