My Book Uses Paparazzi Photos

Dear Rich: Was lucky enough to be offered a book deal by a major trade publisher. The publisher intends to publish my book in both electronic and print format and sell it to all the major book retailers that still exist. The book is to include tons of paparazzi-esque celebrity photos and wanted to know how to go about this legally. Do I have to get permission to use each and every one from the photographer? Are there services that do this in batches? Are there any fair use of public domain instances I should be aware of? Because you mentioned the word "paparazzi," we must take a moment to honor Federico Fellini, whose film, La Dolce Vita (how did Anita Ekberg get that kitten to stay on her head?), introduced the character, Paparazzo, a photographer. That eventually led to the generic use of the term paparazzi, for annoying celebrity photographers.
Right, you had a question. As annoying as such photographers may be, they are still entitled to copyright for the photographs they take (though those copyrights are often sold to celebrity mags, licensing agencies, and TV shows). There are agents and photo reps who can acquire rights for you -- for example, the American Society of Picture Professionals can set you up with a photo researcher. But the costs for such experts may be cost prohibitive. You may find it easier to use licensing services such as PRPhotos.com. For example, we sought to license an image of Brad Pitt for use inside the first edition of a book and could have acquired the license for $200 (see below).

Again, that may seem prohibitive for many but we're afraid that's typical for licensing photos for print purposes.
Fair use and public domain. As for fair use and public domain issues, we don't think you're likely to have much luck with either claims. Fair use is a defense which means you and the publisher have been dragged into a dispute. That's not a good position for an author, particularly if your contract has established that you'll indemnify the publisher. As for the public domain, it's unlikely celebrity photos are in the public domain unless: (1) the photographer donated it to the public domain, (2) the photo was taken by a federal employee within the scope of employment (think of Nixon shaking hands with Elvis), or (3) the photo was published before 1923 (Will Rogers, anyone?).
Creative commons. You may want to look for celebrity photos that are offered under Creative Commons licenses. Finding these photos requires some search engine chops but it can be done. Note that many celeb photos are illegally posted on the web and the interloper labels them as Creative Commons, so unfortunately, you can't always count on the labeling; you need to go to the source, for example, the photographer's Flickr site.