A feature of gssapi-with-mic authentication is that the username can be empty as the server should be able to figure out what username to use from the established credentials.

   3.2 [...] "The user name may be an empty string if it can be deduced from the
   results of the GSSAPI authentication."

http://www.ietf.org/internet-drafts/draft-ietf-secsh-gsskeyex-10.txt

Our modified PuTTY client has support for this; it sends a packet like this

Outgoing packet type 50 / 0x32 (SSH2_MSG_USERAUTH_REQUEST)
  00000000  00 00 00 00 00 00 00 0e 73 73 68 2d 63 6f 6e 6e  ........ssh-conn
  00000010  65 63 74 69 6f 6e 00 00 00 0f 67 73 73 61 70 69  ection....gssapi
  00000020  2d 77 69 74 68 2d 6d 69 63 00 00 00 01 00 00 00  -with-mic.......
  00000030  0b 06 09 2a 86 48 86 f7 12 01 02 02              ...*.H......

but OpenSSH 4.2p1 server sends back

Incoming packet type 51 / 0x33 (SSH2_MSG_USERAUTH_FAILURE)
  00000000  00 00 00 44 70 75 62 6c 69 63 6b 65 79 2c 67 73  ...Dpublickey,gs
  00000010  73 61 70 69 2d 6b 65 79 65 78 2c 67 73 73 61 70  sapi-keyex,gssap
  00000020  69 2d 77 69 74 68 2d 6d 69 63 2c 70 61 73 73 77  i-with-mic,passw
  00000030  6f 72 64 2c 6b 65 79 62 6f 61 72 64 2d 69 6e 74  ord,keyboard-int
  00000040  65 72 61 63 74 69 76 65 00                       eractive.

I think this can be solved in two parts; first, a credential->user mapping. For krb5 gssapi, I'd guess the username to use is the non-realm part of the UPN? 

Second, auth2.c calls pwnamallow("") early, before attempting the gssapi authentication. Untangling this bit of code from the (given) username check so as to allow empty usernames is not going to be simple. The gss token exchange has to complete before a username can be determined.