O que há de errado com chaves estrangeiras?

Lembro-me de ouvir Joel Spolsky mencionar no podcast 014 que ele mal usava uma chave estrangeira (se bem me lembro). No entanto, para mim, eles parecem bastante vitais para evitar duplicação e problemas subsequentes de integridade de dados em todo o banco de dados. As pessoas têm razões sólidas...