How to deal with deploy keys that are orphaned by users

In https://gitlab.com/gitlab-org/gitlab-ce/issues/41466, we see errors 500 due to an assumption that a Key object will always be associated with a user. This leads to workarounds such as https://gitlab.com/gitlab-org/gitlab-ce/merge_requests/16127.

However, on GitLab.com, 5% of the keys table (50762 / 10201992) have orphaned users:

*** PRODUCTION *** production> Key.where(user_id: nil).count
=> 50762
*** PRODUCTION *** production> Key.count
=> 1020199

We seem to intend to destroy a DeployKey if the associated user is destroyed: https://gitlab.com/gitlab-org/gitlab-ee/blob/master/app/models/user.rb#L88

Does setting up a foreign key constraint make sense here? Given that people seem to be using these deploy keys, that seems like it could break a lot of deployments.

/cc: @DouweM, @mayra-cabrera, @yorickpeterse