If they can't verify, they'll ask for someone. You just put down a phone number of someone that knew you during that time who can vouch you weren't out fighting with the taliban. Also, some Regionals barely do those background checks either, they just make sure you're not wanted and are properly licensed.