"Prevent non-key-field row updates from blocking foreign key checks (Álvaro Herrera, Noah Misch, Andres Freund, Alexander Shulgin, Marti Raudsepp, Alexander Shulgin)
This change improves concurrency and reduces the probability of deadlocks when updating tables involved in a foreign-key constraint. UPDATEs that do not change any columns referenced in a foreign key now take the new NO KEY UPDATE lock mode on the row, while foreign key checks use the new KEY SHARE lock mode, which does not conflict with NO KEY UPDATE. So there is no blocking unless a foreign-key column is changed."
Thanks Joel (I assume you are Joel at Trustly) for helping to get work started on fixing this source of deadlocks. I believe your company also helped fund some of the work on the fix. I have been bit by a race condition caused by this myself.
EDIT: And even more thanks to Álvaro and the other developers working on it,
"Prevent non-key-field row updates from blocking foreign key checks (Álvaro Herrera, Noah Misch, Andres Freund, Alexander Shulgin, Marti Raudsepp, Alexander Shulgin)
This change improves concurrency and reduces the probability of deadlocks when updating tables involved in a foreign-key constraint. UPDATEs that do not change any columns referenced in a foreign key now take the new NO KEY UPDATE lock mode on the row, while foreign key checks use the new KEY SHARE lock mode, which does not conflict with NO KEY UPDATE. So there is no blocking unless a foreign-key column is changed."