[whpalmer4]

The built-in search finds projects on hold just fine. However, the thing you are searching for must be in the current view! If you were only showing active projects, for example, the search would fail. Or if you had selected a different folder in the sidebar, the search would fail.

If your search fails, bring up the All Items perspective and try it again. I suspect the number of times an OmniFocus search actually fails due to program error is close to 0 — user error is a different story. The fact that so many people complain about it and are tripped up by it suggests a better UI design would be a welcome improvement, though!