Knuth discusses the rejection technique in section 3.4.1 (2^nd ed, vol. 2), in the context of generating normal RVs from uniform.  His discussion touches on the related issues of long tails and ways to (usually) avoid evaluating the density function.  He also points out that the most general mechanism employs the inverse of the distribution (not density) function, though in practice I’ve not seen it used much except with empirical PDFs (using sorted data as an interpolation table) and for the few standard infinite-support distributions that have closed-form inverses.

I was lax with notation in my original response: PDF conventionally denotes the (cumulative) distribution and pdf the density (derivative of the distribution).  Because the pdf is what usually gets used day-to-day one begins to forget this after leaving school.

-swn