Or maybe you go try to find it since you are the one who brought it up? You're the one with the most chances of finding it since you've already found it once. Maybe it's still in your browser history?
I do doubt that such "company" is able to recover lost bitcoins because to be able to gain access to the wallet again, you're going to need the private key of it. If you such company can give you back the private key of your address by simply pinpointing which address have you had before, then I will be extremely terrified. That means that they are able to get the private key of any address so they are pretty much going to be like Gods in the bitcoin world. They are just going to search the top wallets that have the most coins and get the private key of those addresses. Good thing bitcoin was made so noone will have the computing power and storage to be able to do that. So nope, that company is a fraud and what they are claiming is impossible.