This inconsistency bothered me too--the cleric doesn't tell the gods what to do, it's the other way round. D&D draws from the notion of limited pagan gods, of course, which have their own philosophical inconsistencies.

You point out some possible generic missions for clerics of gods of travel, or gods of a place that want to dispute some other god's domain but not do it Mano-a-mano (as it were).

For gods not of a place, ethical gods, or a monotheism, the cleric has less wiggle-room in his mission. He doesn't necessarily get to travel with the others all the way; he's on call.

I tried playing with the question of "Why would you team up with an unreliable partner?" and came up with the notion of a "geas-ite". He's on his mission, and as long as your missions align you get extra graces along the way, and when he's done you can follow him out of whatever the tight spot is with divine protection--just don't make side-trips. (I'm trying that out with my own attempt at a "dungeon-crawl" story--the rest just want to escape and he offers a way out if they follow him into the worst of it. only 1/3 through--life intervenes...)

I didn't try hard to to make this D&D playable, but it seems straightforward [In a jam and want to bail? Check the cleric's "unread-email"].