While adding some new alias functionality to my setup, it repeatedly failed with an error similar to this, despite my configuration changes:

Recipient address rejected: unverified address: host XXX[XXX] said: 550 5.1.1 
<foo@bar.com> User doesn't exist: foo@bar.com (in reply to RCPT TO command);

Turns out that the negative verification result is cached and the cache is not reset during a reload/restart of postfix.
Thus it must be cleared manually like this:

/etc/init.d/postfix stop
rm /var/lib/postfix/verify_cache.db
/etc/init.d/postfix start