Bob replies to the advert...
First off save the advert. Document what claims are being made as this would help establish that you were seeking a service provided by this person/company. If the company conducts bad business then you, as am unknowing customer, shouldn't be held liable. If you cannot save the advert then save all emails, IMs, etc with the client before you seal the deal. Explain clearly what you need and what you're after then save his responses. All of this will help document and prove the type of working relationship you, as the customer, created.
...would it be as simple as getting a signed declaration from Bob with him saying it is legit?
Yep. That's what I'd do. Create an agreement that, in the case of any legal action related to the audio provided, the composer/sound design (or merchant selling the items to you) will be responsible for any and all costs and indemnify both you and the game. You could probably find one online. If not, talk to a lawyer or ask someone who knows about the law so you can create the appropriate kind of langauge. Keep all records and communications with this artist or merchant. The more mainstream you go - the more likely the merchant will have done due diligence and less likely that you'll face any legal issues related to audio. But if you're dealing with a one-man company the chance is there... especially if they're not well known.
I've had to sign similar agreements or contracts with a clause basically saying that if the music or audio is found to be in copyright - I would be held responsible and not the team or the project.
If so how exactly would that work without 'witnesses'.
I don't think you really need a notary for something like this. Instead I would send the document in an email, which you CC yourself on and explain what it is and why you're asking for it to be signed. Most freelancers have had to do this before and will be fine signing it. Then save both digital and hardcopies of that agreement. If anything should happen you have a very clear paper trail which shows the audio provider understood and agreed to what the clause states.
Hope that helps,