I think some of the larger photo licensing services charge a lot of money for book publishing -- they lump print and ebook together. It's in your best interest to be flexible about which exact photos you need and not have your heart set on a single photograph. There's lots of great photography out there waiting to be discovered which can be had for a dime.
Creative commons photos can be an option, but you need to establish proof that the CC license has been labeled properly. For CC photos I sometimes will still offer a payment to the rights holder to establish good relations and to make them aware of what's going on.
Be prepared for the fact that some rights holder might simply not wish to grant a right to you no matter what you offer.
If you are contacting a rights holder and they are not a big service, you should send a friendly email and name your price up front. Ask for some high quality photo -- the ebook vendors have now been able to accommodate higher resolution photos.
Finally if you want a relatively safe place to find historical photos, check out wikipedia and wikimedia. Their process for vetting photos and giving them the right license is pretty reliable.
Due diligence is the important word here. If you're using CC or public domain photos, you might want to make screenshots with dates of access to use as evidence that you had every reason to believe that the copyright label was accurate. I believe Flickr has a tool to verify the license at a certain date.
The good news though is that unless you have a runaway bestseller on your hands, rights disputes after publishing can usually be handled simply by swapping out the image for future editions. But obviously it's better to clear everything beforehand.
You ask for prices. I can only speak for myself when trying to contract freelance photographers who have individual websites. I generally do low cost publishing.
I usually offer minimum of $20 for a CC photo and actually recently it's been $40 because the $20 was mainly for noncommercial web publishing. If you need other rights (like commercial use or exclusive), expect the price to be higher. I would be willing to pay $50-100 for a high resolution photo, and I know the commercial services can be included to charge 200-1000$ if you're ordering through them.
Indie photographers are willing to entertain offers that are below the rates of
Getty, etc, but you need to send a short email with a dollar amount and intended use. The offer can be low but not too low it is insulting. I think it's fair to state your professional status... Photographers might cut you a break if you convince them you're starting out or dealing with a very small project. And you should be willing to pay the money immediately.
The advantage over stock photography outfits is price; the disadvantage is that photographers can be quirky and may sometimes feel that you're trying to take advantage of them, so you need to respect their interests. Be liberal about giving credit -- perhaps linking to the website.
From another website:
Rights Managed – With this license you only pay for what you’re using the image for. Rights managed licenses define exact use in terms of where, when and for how long an image is being used.
Royalty Free – This is the most flexible option and the most straight forward. You pay a one–off fee to use the image with no restrictions on how you use image, how many times you use it or how long you use it for. You can use the image across multiple projects, forever. There are some restrictions on image use for * reselling’.
I'm sure Royalty Free photos are less of a PITA to deal with, but Rights Managed photos might save you a bit of money. Unfortunately they're structured more around commercial print publishing, and they estimate price by circulation and number of copies. But with ebooks, you can't give that kind of estimate.....Hence the difficulty.
Finally you might enjoy this horror story about what happens when you don't clear photo rights on a photo: http://blog.webcopyplus.com/2011/02/14/legal-lesson-learned-copywriter-pays-4000-for-10-photo/