Partitioning and partial indexes both have considerable limitations that you might need to work around. That said normalization exists for a reason and having multiple "person" columns in a table is a form of duplication that if left presents just the problems you are seeing.
I suspect your SSN should fit onto the message-person table.
The following doesn't make sense - if the SSN is sender unique then there is no expectation that a receiver would not receive two messages with the same SSN from different senders.
ALTER ... msgs_to_me ADD CONSTRINT them_uniq UNIQUE (THEM,SSN);
