Ugh that sounds like a nightmare! And I thought Melbourne venues were tough.
Have you considered or looked at theatres and lecture halls at perfoming arts or other colleges? Melbourne used them before finding their current venue.
An alternative might be to use a smaller venue but run it over a couple of nights? I don't know how the licensing works with that though. Not the preferred option obviously as an organizer, but a few cities have held multiple night events and might be able to provide advice.
Hope that's of some use