Many mil bases here in the East are moving to a 380-390 Mhz range P25 trunk; this can currently only be trunktracked with a Uniden 396, and presumably a Uniden 996. I understand that this trend is nationwide; in the past, I think I have seen some listings that some mil base fire depts are in the 160 mhz range. However, don't take that as gospel - the folks in your area are most likely to have the straight scoop.
Another area to check, would be the 406-420 MHz, federal government band. They could be operating in conventional or trunked mode in that area. Let us know if you find anything?
According to M/A-COM, they just recently installed a new Project 25 TRS at Mountain Home AFB. According to information in their official press release, the new system operates on VHF-High band. However, most Project 25 TRSs for the Dept. of Defense are on UHF.
The frequency spectrum most likely to support this new TRS are:
Check 173.5875. I have seen this used by many Air Force Bases for Fire Dispatch and Crash Nets.
Also try searching 164.000-174.000, 148.000-151.000, and 138.000-144.000.
The base that I was stationed at had nets in all of those ranges.