For a cell phone based solution, check with Verizon. They are very prevalent in the Virginia area, and may have the best coverage.

Ensure the phone is 2G and 3G compatible, and that the user can manually select 2G or 3G. Many 3G phones will continue to search for a 3G signal (that isn't always available in rural areas), even though there is a perfectly strong 2G signal available.
This then causes the phone to have no signal.

Manually selecting 2G will also increase battery life, as the 2G radio inside the phone uses less juice.

As to renting a SAT phone, I have no experience.