1 Personally, I found the Working Holiday Visa allowed me to leap many of these hurdles by entering the country with rights to work right away. However I was young enough to to do so. SMC takes a bit too, so it may be better to find employers that will do a working visa in the immediate(free?) and then step up to the SMC.
2 I never cold-called employers, and have never heard of people doing so.
3 I mentioned visa status in my cover letter, not CV. CV is my skills set, not my story. However your status sounds tenuous to employer, i.e. I'm hoping to get a visa if you give me a job....
4. As I said I wouldn't cold call. I wouldn't risk phone quality myself, but that's just me. Doesnt' seem worth risk for a few bucks. Your call.
5. I never provided references, but simply state they were available. I still do the same. I want to be the stop-gate between prospective employers and referals. Plus it provides me a chance to catch up with my references, relationship building.
Another hint, format your resume in no newer than office/word 2003. Most offices here are still on older systems here. PDF is another option, though I have had a recruiter friend tell me he had one firm not accept this.
Finally. Seek.co.nz At least in my field it's the number 1 site.