The SSH agent handles signing of authentication data for you. When authenticating to a server, you are required to sign some data using your private key, to prove that you are, well, you.

As a security measure, most people sensibly protect their private keys with a passphrase, so any authentication attempt would require you to enter this passphrase. This can be undesirable, so the ssh-agent caches the key for you and you only need to enter the password once, when the agent wants to decrypt it (and often not even that, as the ssh-agent can be integrated with pam, which many distros do).

The SSH agent never hands these keys to client programs, but merely presents a socket over which clients can send it data and over which it responds with signed data. A side benefit of this is that you can use your private key even with programs you don't fully trust.

Another benefit of the SSH agent is that it can be forwarded over SSH. So when you ssh to host A, while forwarding your agent, you can then ssh from A to another host B without needing your key present (not even in encrypted form) on host A.

TL;DR

The most helpful comments from @forcefsck. Unfortunately he didn't fill the answer so I was unable to award the bounty. In short, the answer is PEM + RSA1 + new openSSH format which is described in the question and the main problem was with PEM.

The long one & Bonus

OpenSSH is using parser from openSSL (PEM_read_bio_PrivateKey()), which has the only return value for all the failures (NULL) and if it fails, openSSH expects it was because of wrong passphrase.

Without OpenSSL

I just tried to build OpenSSH without OpenSSL support (--without-openssl configure option) and the behaviour is "correct":

# ./ssh-add <(echo "")
Error loading key "/dev/fd/63": invalid format

Fix with OpenSSL

The other thing is how to fix it. The poke comes from ERR_get_error() function and their friends which should allow us to distinguish between different errors.

Wrong passphrase errors

# ./ssh-add /tmp/rsa
140480353842840:error:0906A068:lib(9):func(106):reason(104):pem_lib.c:457:
Enter passphrase for /tmp/rsa: 
140480353842840:error:06065064:lib(6):func(101):reason(100):evp_enc.c:592:
140480353842840:error:0906A065:lib(9):func(106):reason(101):pem_lib.c:482:

Reasons: PEM_R_BAD_PASSWORD_READ, PEM_R_BAD_BASE64_DECODE, PEM_R_BAD_DECRYPT.

Parse error codes

# ./ssh-add <(echo "")
139656018548376:error:0906D06C:lib(9):func(109):reason(108):pem_lib.c:701:Expecting: ANY PRIVATE KEY

or this:

140654301202072:error:0906D066:lib(9):func(109):reason(102):pem_lib.c:809:

Reason: PEM_R_NO_START_LINE, PEM_R_BAD_END_LINE, but there might be more possibilities.

Solution?

Adding some more checks for OpenSSL errors should give us an option to choose which error we want to mark as "format" error and which is "bad passphrase". This is located in function sshkey_parse_private_pem_fileblob() in sshkey.c on line around 3800.

unsigned long e = ERR_get_error();
if (ERR_GET_REASON(e) == PEM_R_NO_START_LINE ||
    ERR_GET_REASON(e) == PEM_R_BAD_END_LINE) {
        r = SSH_ERR_INVALID_FORMAT;
} else {
        r = SSH_ERR_KEY_WRONG_PASSPHRASE;
}