Hay varios problemas potenciales, así que abordémoslos por separado.
En primer lugar, la zona de llegadas del aeropuerto. Los aeropuertos australianos disponen de zonas de llegadas internacionales. Estas zonas no disponen de más servicios que los cuartos de baño y algún que otro asiento, y posiblemente una tienda libre de impuestos (MEL tiene una, pero puede que esté cerrada en ese momento). No están pensadas como zonas para que los pasajeros simplemente deambulen por ellas: se espera que los pasajeros pasen por inmigración y entren en el país, o pasen por el control de seguridad de tránsito y entren en la zona de salidas internacionales (que requiere una tarjeta de embarque/vuelo de conexión). Alguien que simplemente merodee por esa zona sería tratado con recelo, y no sería de extrañar que el personal de seguridad se fijara en ti y se interesara por ti (incluyendo la posibilidad de que consideraran que podrías transportar drogas, etc.).
A continuación, la inmigración. Aunque el aeropuerto de Melbourne está abierto las 24 horas del día, inmigración no lo está. Las últimas llegadas internacionales se producen en torno a las 23.00 horas y, una vez procesados esos pasajeros, la zona de llegadas queda despejada y se cierra inmigración. Es probable que esto no ocurra hasta después de medianoche, pero no hay garantía.
Luego está la fecha de llegada. Las llegadas a Australia están automatizadas, y muchos pasajeros ni siquiera tratan con un humano a su llegada, sino que utilizan puertas automatizadas que se correlacionan con la información extraída de los datos de los pasajeros proporcionados por la aerolínea. No sé exactamente cómo funciona esto en cuanto a la fecha de entrada, pero no me extrañaría que tu fecha de entrada se fijara en la fecha de llegada (es decir, cuando aterrizó el avión) aunque no entraras en inmigración hasta después de medianoche. No tengo nada que respalde esto de un modo u otro, pero es un riesgo...
Por último, está la cuestión de si se le permitirá embarcar en el vuelo. Si tu visado exige billete de vuelta (algunos sí, otros no), la aerolínea que te lleve a Australia podría darse cuenta de que, aunque tienes uno, está fuera del plazo permitido en función de la hora de llegada de tu vuelo. Probablemente sea poco probable, pero como mínimo es un riesgo. Si no necesitas billete de vuelta, no habrá problema.