This is a no-brainer. The client is always responsible to provide content UNLESS they are willing to pay for it to be recreated. Doesn't matter if you hire someone to shoot it/re-create it, do it yourself, go buy it from stock. All this things (other than the client providing it) should cost money. Even if you have to look for it on the web. Time is money!
In all of my contracts it explicitly states that the client is financially responsible to provide content unless arrangements are made to HIRE me to create it. If I go to a stock site and grab an image, it has to be in the budget and I always markup the cost to cover my ass. Time is money!
If a logo, image, or any other content is provided that doesn't meet the requirements of the job, I always call the client back and ask them how they want me to proceed. There are two options. First is, get the correct item to me. 2nd option is to hire me to fix the issue (if possible), or hire someone else to provide the content. If they say "... just go on the web and grab something". I counter with... "Okay, I'll get to that done soon as you sign-off on this change order, because it's going to cost you extra for my time." If they say, just use a lowrez version, I tell them no and suggest that I retrace it for a minimal cost. If they say no, then I finish the job and never work with them again.
The only other option you would have is to bury the costs in your initial proposal if this happens frequently. Add a "content modification/research" fee into the job order. If they ask you what that is, just tell them it's to cover for all those additional costs that come up whenever you are trying to provide an excellent product.
And the answer to your original question is probably to redo it in Illustrator for a reasonable fee. You might be able to get away with auto-trace if you're in a hurry.