Foreign key quandries

Going through the issues in doing dirty reads in foreign keys I've come up
with a few cases that I'm fairly uncertain about how to handle with
regards to deadlocks and figured I should ask for advice because I think
I'm missing something painfully obvious, but don't get large enough blocks
of time to think about it to figure out what it is.

I'd thought maybe it'd be enough to say which type of
thing on which constraint and use that to basically say that
we don't need to wait on a transaction that's waiting on us
due to a modification to the other table, but AFAICS
that lets through a bad case:
T1: insert into fk values (2);
T2: delete from pk where key=3;
T2: delete from pk where key=2;
T1: insert into fk values (3);
If T1 doesn't wait in this case, you can get into a case where
a bad row is inserted into fk if you then have:
T1: delete from fk where key=2;
T1: commit;
Now there's no row to make the second delete fail but
transaction 2 still can't commit due to the fk row with key 3.

I'd then thought of doing something based on what row/value
transaction 2 was waiting on, but that has problems.
Given a foreign key with no referential actions and a
sequence like:

Transaction 1 inserts into the foreign key table a row
with a referencing key of 2.
Transaction 1 checks the foreign key
Transaction 2 deletes the primary key rows having keys
2 and 3
Transaction 1 inserts another row into the foreign key
table with a referencing key of 2.
Transactions 1 and 2 start checking the foreign key.

AFAICS, transaction 2 needs to wait since there's already a
row it can see in the foreign key table that's not yet committed
(so it doesn't know if the delete works or not). We can tell
transaction 1 that it doesn't need to wait on transaction 2
because transaction 1 is inserting a value that transaction 2
will see in its check, thus we're saved from the first case.

However, this has the potential to deadlock if we had for example,
inserted a foreign key table row of 3 rather than 2 as the second
insert in transaction 1 and the delete check for 2 went first. If
we knew that it was also going to be checking the 3 rows, we'd be
safe, but then we've got to keep that information in some way that's
visible to other transactions AFAICS. And, if the checks were
done in the order delete check for 3, delete check for 2(t2 blocks),
insert check for 3, we'd be back in the state of the first example.
:(