I can think of a couple ways you can do this.
1. Possibly the easiest way would be to use Javascript's AJAX to send a request to a page that can query the database and check availability.
2. Submit the form to the final page and check availability then. You can always store the forms information in a session so the form can be re-populated if you have to go back. And a far as any files that have been uploaded, the saved files name can also be stored in the session so it can be deleted if the users change their mind.
I am sure there are several ways you can go once you understand what you can do.