Individuals holding Australian permanent residence status are eligible to be employed by Airservices Australia.
Still that Catch22 boll*cks!
Airways New Zealand are indeed desperately looking for ATCO's. And this time they even help you getting residency.
http://www.airways.co.nz/careers/vac...acancy0630.asp
This would only be an option though, if you like abknoxious micro management... (markjoy might know what I mean
)