if the radiator doesn't flow as much as it should (i.e., not the same though-put at a given pressure as the oe radiator) then it won't cool engine adequately. raising rpm raises pressure from the water pump pumping more so the radiator now lets some more pass through it.Question for you - If it's a sub-standard rad...why would revving the engine (e.g. pop into 2nd) immediately drop the temp from 'critical overheat' to 'everything good' in no time flat, and why would the problem not exhibit at stop, only highway speeds that involve hills? Those don't point to a crap rad, or thermo.
i'm suspect of both the radiator and themostat. the bottom hose should not be cool to the touch, to me this indicates in-adequate coolant flow. since the water pump is oe Nissan (and you had the same issue before changing the pump change) my bet's still on tthe radiator (with the thermostat right behind). I guess it could also be some sort of physical obstruction in there but that seems less likely (but who knows what the emergency mechanic did).
I think air in system being the issue is unlikely. with all going on, most air should have bled off by now or at least be at top of radiator leaving it visibly low which would have been notied by now.