The new radiator definitely solved mine. Even idling in a drive-thru lane for a long time on a 100 degree F day with the A/C running, the coolant temp gauge never rises past mid-scale, and the oil temp never goes over 225 F.

My old radiator would still flow water from a garden hose freely from side to side, no real signs of cloggage/blockage but I highly suspect the insides of the aluminum core tubes are probably lined with corrosion and scale that's making a very good heat insulator and not letting the heat transfer from the liquid coolant to the outside of the tubes and fins. When I have time, I will pry a tank off the side of the old radiator and have a look at the tubes and take some photos.

I've been told that aluminum core radiators only last about 15 years and then start going downhill and become very inefficient at dissipating heat. My experience with having to replace an aluminum core radiator in my 2000 Chevy pickup earlier this year (also was leaking, and suffered a hard-stuck thermostat), and now the radiator in my Audi, seems to support this approx 15 year useful lifespan of these radiators.

I was able to find my replacement radiator (Nissens aftermarket brand) for the Audi for only US$106 shipped to my home, from RockAuto.com but I'd reckon getting a replacement in NZ will likely cost a bit more.