This is pretty easily solved by using different keys for each service you wish to authenticate with (the same idea as using different passwords, basically). I already do this when pushing to GitHub over SSH versus SSHing into my own server.
Or an interactive key selection on the command-line? With a 'Remember my choice' option. These could be relatively easy UI enhancements for a command-line SSH agent.
You then must maintain different agents, one for each distinct set of keys you want to use. The ssh-ident package helps do this.
Or, you must insert a filter proxy between the real agent and the ssh client. The ssh-agent-filter package helps do this.