I am by no means an expert on immigration, but here's my take to this.
The requirement is "Authorization to work in the United States without sponsorship". The keyword is "sponsorship". To apply for the E3 Visa, you do not require employer sponsorship, just a offer of employment from the company, so technically it would still count. Also, for Australians & NZ Citizens there is another visa called the J1 Visa. It basically allows you to work for 12 months in the US, similar to the Working Holiday Visa we have in most commonwealth countries. Most companies terms and conditions require "Authorization to work in the United States". After you get your J1 Visa and land a job at , you can simply hop across the border to Canada or Mexico and visit a US Consulate with your job offer in hand and apply for the E3 Visa, and bypassing the two year return to home country restriction on the J1 Visa.