Evilg: RCD is mandatory, and they can be expensive depending on whether they install and RCD socket (expensive) or an RCBO in the switchboard to replace the existing circuit protection with an RCD/overload breaker.

It depends on the suitation, if a new circuit has to be run the it needs RCD protection, if you are connecting to an existing circuit no RCD required.

My understanding is if a new power outlet is installed it must have RCD protection. 

As mentioned above it depends on the situation. Many of these situations are also descibed above.

In a very broad genalisation if the socket is connected to an existing circuit no RCD is typically required unless it's being fitted in a risky or wet area. If a new circuit is required a RCD is required.

Guys I don't want to get on my high horse here, but I am a registered electrician, electrical engineer and have electrical inspectors working for my company.

I refer you to AS/NZS 3000:2007 clause 2.6.3 and specifically

You absolutely WILL need an RCD if you are extending a subcircuit and adding a socket-outlet to the end of it. This RCD could be installed at the board thereby protecting the entire sub-circuit, or it can be installed to protect downstream of the original circuit. Either way the new socket-outlet must be protected.

And at the end of the day the OP is talking about adding an additional socket-outlet on the end of a sub-circuit, in a residential situation.