They will queue to the point before they can be delivered to the Exchange Server.
So, it depends! :)
If the Exchange Server is a mutil-role server and its the only hub transport in the site, then they will queue on the hop before its delivered to the hub transport. THat could be an inbound SMTP gateway or if you accept directly from the internet, they will
queue on the sender's server.
If there is a in-site hub transport still up and running, they will queue there until the mailbox store is mounted again. It could also queue somewhere else in on org - It all depends on the topology.
