結論（の一つになり得るもの）

Hostにgithub.comと指定していない。

つまり、以下の内容ではダメです。Permission denied (publickey)と盛大に怒られます。

Host github
  HostName github.com
  Port 22
  User git
  IdentityFile ~/.ssh/foobar.key
  AddKeysToAgent yes

備考

とあるページで「Hostは任意に設定可能」というのを真に受けた結果です……。

あともちろんGitHubに限ったことではないです。Hostには接続先のアドレス（IPアドレスなども）を記入します。