Even though i'm not in the business of designing and setting up radio systems, I do think that if DPS was serious about it, they could upgrade their existing VHF system and get better reception, without having to spend a huge amount of money.
Think about it: add repeaters in areas where coverage isn't that good (the Tennessee Highway Patrol did the same thing) or just add repeaters. Add CTCSS tones to eliminate interference from other posts or out of state users. Add other frequency pairs. In other words, they could do more - at probably less cost - without have to go UHF or 800Mhz. The Forrestry Commission is the best example of how to build a system - and they use "old-hat" VHF!
Trunked systems are the latest thing go have. You've got the public safety equivelent of keeping up with the Jones', with the justification for the new system is that the old one is antiquated. That's kind of a pet peeve of mine, because it may be the infastructure (you may not have repeaters in newly annexed areas) or hardware that is antiquated and not the frequencies. I did read that one of the reasons that Montgomery went to a trunked system was to replace its "antiquated UHF system."
I have been doing research on the new DPS system, and most of what i've found has dealt with interchange of data for fingerprints, criminal records, mugshots, etc. Starting with the Motorola press release, I learned that the name for the system in Alabama is called LEISS, and its part of the Integrated Justice project. Radio communication wise, i've only been able to find out two things as part of that project: 1) I saw the minutes from a meeting that mentioned that DPS had checked into 700Mhz, but it was too expensive, and 2) the statement that DPS is looking into a new radio system. That's all that i've been able to find. The LEISS steering committee did survey state/county/city law enforcement agencies, and in addition to computer/networking information, they did ask about radio communications used by those agencies.
As far as trunked 800Mhz systems in hilly areas, two years ago I worked a missing person search in the Graysville area with the Jefferson County SO as a Ground Team Leader with Civil Air Patrol. The SO Sergeant in charge told me that their 800Mhz system didn't work in that area. In fact, the deputies that we were searching with were using Motorola FRS handhelds to communicate!
Warren