Fremantle
So it turns out that the Map and Chart shop in Freo does print Openstreetmap maps to order. It seems like they can do any A-size paper and any scale, on nice paper with borders and legends and titles.
I'm going to get one of Rottnest! (As soon as I've had one more bash at it in Josm, to catch any obvious errors.)