Non issue then (the RE4). If you look at the statute, you can see the law is clear...
E. The department of public safety shall issue a permit to an applicant who meets all of the following conditions:
Then it lists a bunch of factors...
For example, you must be a valid AZ resident OR US Citizen (gotta love AZ), you need to be at least 21, can not be mentally ill, must me "legal" (again, gotta love AZ), need to complete the firearms safety program.
Now, this part is interesting...if you have at least a "general" discharge, your good...that will satisfy the firearms training requirement...now that I must say is odd...heck, I was enlisted in the Navy
and had a class on the 45...but never shot the darn thing...again gotta love AZ.
But even if you got an OTH, you can simply attend a proper training course to qualify
Let me know if you have more questions