You have a good point about the exhaustiveness required to ensure the best possible outcome. In that case the ability of the genie to act "safely" would depend upon the level of the genie's omniscience. For example, if the genie could predict the results of any action it took, you could simply ask it to select any path that results in you saying "thanks genie, great job" without coercion. Therefore it would effectively be using you as an oracle of success or failure.

A non-omniscient genie would either need complete instructions, or would only work well where there was an ideal solution. For example, if you wished for your mother to be rescued by a fireman without anyone dying or experiencing damage to more than 2% of their skin, bones or internal organs. The difficulty is when not all your criteria can be satisfied. Things suddenly become very murky.