Image copyrights on prototypes sent to publishers

I'm developing a card strategy game roughly based on historical times (you can have citites like Alexandria, Rome, etc.). During playtesting, I've just picked random images off the net and copied them on to cards. It's for personal use so I see no problem with that use of images.

Here's my question(s). When I put together a nice prototype to send to publishers, I want to put images at the top of city cards (i.e. the pyramids for an Egyptian city, the Coliseum for Rome,etc.).

Do I need to obtain permission from the owners of those images even if it is just a prototype? What if it's just some random image on the net, how do you 'obtain permission'? Just because the image is on someone's site doesn't mean they necessarily have the authority to grant permission to reuse the image (it may belong to an unknown party and the site's owner just grabbed it from somewhere else as well). My thought is that this is still a personal use (in a prototype sent to a publisher). I'm not planning to sell the game with these images included (but maybe this needs to be clear with the publisher, that if they want to publish the game they'll need to get authorization to use these images or get their own?)

The follow up to this is, would a typical publisher expect that my art be: original, already authorized for use in the published version of the game, and/or do most publishers like to see some art to visualize the game, but they fully expect to insert their own professional art if/when the game is published?

Thanks!