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).
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.