The phone looking for signal issue could have been solved when cellphones first came out even. The phone internally knows what cell tower its pinging. You flag ones around the fringes of known no service areas like a natural park. If the user hikes off into the woods, the phone is capable of knowing its going into a no service area based on the id of last cell tower its pinged and the fact that its just lost signal for longer than 30 seconds. At which point it could switch to hunting for signal every 10 minutes or something with better compromises for battery life and realistic expectations given the area.