Everyday encounters with NP-complete problems Mark Dominus collected a few examples of polynomial-time reductions from various NP-hard problems to “regular expression” matching. Envisioning polynomial-time verifications isn't an enormous leap.

How do you illustrate the class NP-complete to undergraduates or to friends in other fields who wanted to understand the recent fuss over Deolalikar's paper?
My favorite example to use with non-CS friends is this one:

Abraham, A. Blum, Sandholm.  Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges.  EC07.

Kidney exchange markets are essentially a restricted form of cycle cover.  I like this example because a) it's easy to explain the gist(if you leave out some of the more technical details) and b) it's one of the few instances I know of where better algorithms can literally save lives!

My second favorite example is the hospitals-and-residents problem (aka the college admissions problem).  Each hospital ranks all residents (graduating medical students) and residents rank hospitals.  Each hospital has a certain number of slots.  From there it's a stable matching problem and can be solved in polynomial time.

But in reality, couples can enter the system (yes, there is indeed a system) together, so that the system won't, for example, split up married couples who are both applying for residency.  The addition of couples makes the problem NP-complete.  In addition to being easy to explain, this nicely demonstrates how the introduction of long-range connections can induce NP-completeness.