Well, generally every language has some quirks in its grammar, but as for your examples, を is the only option and に is never used. I sense from your statement "I would've thought に would be used in place, but instead を is used" that you may think or be taught that case particles each represent some kind of "universal" trait, but they are actually decided by loose conventional rules much like English choice of prepositions, that you can't make nearly perfect prediction from its meaning.
探す indeed has two kinds of noun alignment:
[place]を探す but neither can take に. You wouldn't see it except as a part of adverb: 効率的に探す.
Don't be fooled by the English translation. The answer you expect for "What do you do to Grace?" would usually not be "I do [noun] to Grace." but "I [verb] Grace.", isn't it? In that case, you use the phrase "do what" to asking another verb; it is a pro-verb, more specifically, interrogative verb.
English speakers have to work around the lack of pure interrogative verb by forming an expression "do what" (i.e. "what" as dummy object) and push the original object out as indirect "to" argument. Japanese doesn't have one either, but fortunately we have どうする (どう is an adverb) that doesn't take up the object slot, so that the true object remains the object.
What are you going to do to Grace?
I will send Grace back home.