I'm going to throw out a somewhat radical, even heretical, idea: that foreign key constraints, as traditionally implemented, might not be worth it.  What?!? you say.  Foreign keys are essential to your data integrity?  They're worth the minor performance impact, right?  They're also worth the hassle of dealing with them?  OK, fine.  But read on.

Foreign key constraints have other less obvious drawbacks.  Consider this: the foreign keys in your database probably make it difficult or impossible for you to prevent deadlocks.  Let's say tables A and B are related by a foreign key (B -> A).  Now let's assume Alice wants to (within a transaction) insert records in both tables, and Bob wants to delete records from both tables.  Because of the foreign keys, Alice must access the tables in this order: A, B; while Bob must access them in this order:  B, A.  Whenever you have multiple clients accessing more than one resource in a different order, you have a recipe for deadlock.  Alice locks data in table A, Bob locks data in table B, and then they wait on each other.  Forever, in principle.

Now a supposedly smart database like SQL Server will detect this deadlock and shut down one of the transactions ("You have been chosen as the deadlock victim.  Buh-bye.").  But that's not very nice, is it?  Now the caller has to handle that scenario and retry.... ugh.   It's also possible to reduce the likelihood of a deadlock by partitioning data, using finer-grained locking, shortening transaction times through various means, and/or specifying loose transaction isolation.

One very good idea is to access your tables in a consistent order - if you can pull it off, this will completely prevent deadlocks, though you will still get some temporary blocking.  This is almost always worth it for a high-volume application.  The presence of foreign key constraints, however, will prevent it from being bulletproof if you must support both adds and deletes, for the reasons mentioned above; adds go top-down, but deletes go bottom-up, which means you're not accessing things in a consistent order any more.

So what to do?  Besides the ideas above, you could consider removing the foreign key constraints from your database, if you're willing to write (and test) the significant application code required to ensure that your data integrity is bulletproof.  A side benefit of this is slightly better performance.  To date I have not found it necessary to go to this extreme.  But here's what I would like (Microsoft, are you listening?): I want constraints that are not checked until my transaction is committed.  This idea is not new; in fact Oracle has had it for quite a while, and Microsofties have been discussing it for a a while.  Here's one blog entry that talks about pros and cons of the idea.