Lawyer, and have him show that there is no bill of sale requirement in Arizona between private parties. Have you ever had the gun in for work done, the pawn shop, anything where there is an official record of the serial number?
Does the police report of the incident have the serial number listed? If it the numbers were run at the time of the arrest and didn't come back stolen, I'd wonder why they need something else to give it back...
As for cheap lawyer, call the NRA, and see about Legal Aid in your neck of the woods. Sometimes you can get a legal opinion for a few dollars through that outfit, but no guarantees. Good luck!
Whoops, just realized you were on a res. You might want to just start looking for a new gun. If you're not a tribal member, and you're carrying on tribal lands, you could might have dodged a BIG bullet, as state carry laws run a distant second place on the reservations. Check with a lawyer or Legal Aid, but with reservation PD they might just tell you no dice.