Be careful about visa on arrival as the Omanis are apparently now saying that you now need e-visa. They visa on arrival counter is still open, but who knows when that will change. More concerning is if the "new rule" gets put into the TIMATIC system used by the airlines to determine whether you will be admitted into the country. If TIMATIC ever says you need an evisa, they'll deny you boarding even if the Omanis will issue you one at the airport. Personally, I always find evisas a pain (it may take you an hour or two to figure it out), but it's better than being denied entry. I'd do e-visa now as an "insurance policy."