Last time I was there (Thursday) JB Hifi had 16gb 'Sandisk Ultra' (20mbps) memory cards for $45. I was thinking of picking up one or two after pay day (hopefully still on sale then!). Otherwise eBay also have the same ones for sale. Might be worth a look?
And if you have a laptop or eeePC at home that you can pack away, leave it in the hotel and just load the photos off your camera on to it if you're low on memory cards/space.