I've done a some basic tests to try narrow down the problem. At first we thought it was our router, so we've switched routers. All PCs in the house are connected via Ethernet, so it's not a wireless problem.
I've checked pings to NZ websites during the spikes, and those are perfectly normal (around 10-15ms all the time).
Pings to Australian websites spike at the exact same time as the game spikes, which is understandable because it seems most game servers we play on are in Australia. Normal pings to websites such as whirlpool, telstra are in the 45-50ms range. During the spikes, these rise up to about 600ms.
These are very consistent and happen constantly. Is it possible that this may be a problem at the local exchange or is it most likely still localized to our house?