To stay legal, UHF is limited to 5W, so the range (without repeaters) is limited - particularly as UHF is pretty much a "line of sight" signal which doesn't work well in heavy trees or mountainous terrain.
HF (i.e. Codan/Barrett/"RFDS style" radios) can use higher power and get incredible range, but is highly dependent on weather conditions - and generally requires a knowledgeable user. (Note that AM CBs also operate in the HF band, and SSB operation can also achieve incredible range when weather conditions are correct.)
"Satphone" isn't the answer - well, not any more than "a radio" is the answer. The cheaper satphones (i.e. Globalstar) operate on what's referred to as a "bent pipe" principle, where coverage is only available when the satellite can see both the phone and a base station - at the same time. Because the satellites don't talk to each other, the "pipe" picks up the signal and "bends" it back down. Last time I checked there were only three Globalstar base stations in Australia, so they can be really hit and miss in remote areas - you may receive coverage for only a few minutes every few hours.
However, satphone is a fabulous solution - if you go with the right operator, which typically costs more. For example, the Iridium network bounces signals between satellites to find a ground station, so if the phone can see a satellite (which is most of the time) you'll typically get coverage. Finding somebody to hire out an Iridium satphone can be tricky - most seem to want to push Globalstar, probably because it's cheaper. Also remember that it's higher frequency than UHF, so it's even more affected by heavy tree cover and steep mountains - if the phone doesn't have "line of sight" to the satellite you could still be in trouble.