For utility, I'd say LWP, since I seem to be using it in some interesting way every day.

For solving problems that I couldn't even solve myself by hand, that'd be Parse::RecDescent, or nearly anything by "The Damian" these days. Well written, well documented, and does something unusually cool and often useful.

-- Randal L. Schwartz, Perl hacker