Our alternative solution is to fly to Shiraz instead and make our way South from there. Omanian budget carrier Salam Air serves the connection three times a week (Tuesday, Friday and Sunday).
My best bet for a direct flight to Bandar Abbas from Muscat was Kish Airline.
I tried to call Kish Airline's offices but to no avail (I was using SkypeOut). I also sent them multiple e-mails and faxes which all remained unanswered. However, some of my Iranian friends managed to get in touch with them. Apparently, the airline's Muscat-Bandar Abbas flight is not yet available this year and anyways it will be connecting via Kish. There is no direct flight.
On top of that, I'm afraid it could be quite a challenge to book these flights online. I spent hours with Kish Airline's Persian booking page (and Google Translate and a Persian calendar) but couldn't find any flight for any destination on any date. If someone was to pass this challenge I assume the next one would be to find a way to pay for your ticket. Foreign credit cards are usually not accepted in Iran.
I think the only reasonable chance is to go through an Iranian travel agency or some other contact in the country or show up in person if that's an option.
Any further details are welcome.