My opinion only, but I'm perfectly comfortable moving around in that country (or anywhere else, for that matter...) without a SPOT type device. In a couple of weeks, most of your planned route, I don't think you'd likely have to wait long for someone to come by if it came to that.
On the other hand, for myself, I've found a GPS worth carrying. Never really been too turned around down in there and never had any navigation problem a map and compass couldn't easily handle. But, they don't call it The Maze for nothing and I have found myself double checking and verifying which fork I'm about to turn up often enough to make the raw convenience of a mapping GPS worth having, to me.
Sounds like a really great trip you have planned. I visited Happy Canyon for the first time four weeks ago - awesome narrows!