Is a company's dark web search really effective at proving my info is not there?

This borders on being a scam. The "dark web" does not contain what people think it does, and it is not vast or all-encompassing. Hackers do not just randomly put stolen information on the dark web, and the overwhelming majority of underground transactions involving stolen data do not occur on it. What these companies actually do is scan public databases such as public leaks and Pastebin posts for certain keywords, and alert you if any are found. They use the term "dark web" for marketing reasons only.

Now, I'm not saying that these companies are completely useless or that they are never able to identify stolen information, but they do not do so by searching anything you would call the "dark web". In fact, it is so much of a buzzword that what they are doing now is no different from what they were doing before the term became well-known and before it became entwined with so much mysticism and FUD.