I'm going to agree with you, mainly because the primary translation, "My wife does not find her shoes", while accurate, is a really obscure thing to say in English. With DL's history of weird sentences this is no argument in itself, but logically your translation makes sense and would be a more common thing to hear.
Of course, the literal version of "My wife cannot find her shoes" would be "Mi esposa no puede encontrar sus zapatos", but if we look at "Mi esposa no encuentra sus zapatos" as commenting on a scene we get "My wife is not finding her shoes", which is even weirder English than the primary translation. We'd instead say "My wife cannot find her shoes."
The way I look at it with no other context it would be sheer madness for a native Spanish speaker to really simultaneously consider all possible interpretations. Which means one interpretation likely pops into their heads. With no other context we probably have to assume the shoes belong to either the person making the statement or his wife. And since "sus" does not expresses first person ownership(like "mis") they are likely the wife's shoes.
While I definitely understand your inclination to use did here as it is the more natural way we would say this sentence, it is not accurate because did is past tense and would be "no encontró". The proper translation is "My wife does not (doesn't) find her shoes. While it sounds funny on its own, think of it in context. "Every time we are about to go to a football game, conveniently, my wife doesn't find her shoes as quickly as she could."
Also, encontrarse can be used in the "to feel" sense. For example, "Even though I have tried to convince her otherwise, my wife does not find her shoes frivolous."