Cloning a public project via SSH fails when logged user has a deployment key not assigned to the project.

I have a public repository. Trying to clone it from a user who has a registered deployment SSH key which is not assigned to the project fails. This seems counter-intuitive. Moreover, cloning over HTTP works.

Environment:

Gitlab 7.5.1 (commit 36679b57)