Looking for suggestions

I've got a situation while looking at
match partial fks that I figured I'd ask for
suggestions about, in case there's a better
solution than the one I've come up with.

I believe for referential actions on match
partial, we need to lock all referencing rows
in the fk table as well as all rows that those
rows reference in the pk table. The thing that
I'd be worried about is:
fk table has a row that is a referencing row
of two rows in the pk table.
one transaction tries to delete one of them
while another tries to delete the other.
each one thinks the fk row is not a unique
referencing row (since the other row still
exists in their world)

I would just do a check in an exists clause,
but then I don't think I can lock the rows (since
for update doesn't seem to exist in subclauses
and an outside one doesn't seem to affect rows
in the subclauses either) I'm also worried
about potential deadlocks (I'm assuming that
ordering the select for update's output won't
affect the order the rows are locked in).

So, I've been thinking I can do something like:
get all the referencing rows for this table
for each one,
get its referenced rows (other than this one)
if none, do any action necessary

But this seems less than optimal and I'm reasonably
certain I'm just missing something obvious (my brain's
decided to take a vacation recently :( ).