keyboard-interactive trouble

[der Mouse <mouse%Rodents.Montreal.QC.CA@localhost>]

I'm trying to add keyboard-interactive authentication to my ssh.  Doing
some basic interop testing against

SSH-1.99-OpenSSH_3.6.1 NetBSD_Secure_Shell-20030917

I see something odd.

Specifically, looking at the packet trace, I see (starting just after
the SERVICE_ACCEPT for "ssh-userauth"),

(265) Out data (36):
(266)    0   32 00 00 00 05 6d 6f 75  73 65 00 00 00 0e 73 73  2····mouse····ss
(267)   10   68 2d 63 6f 6e 6e 65 63  74 69 6f 6e 00 00 00 04  h-connection····
(268)   20   6e 6f 6e 65                                       none

My USERAUTH_REQUEST, trying to authentication with method "none" to get
a list of methods.

(269) In data (45):
(270)    0   33 00 00 00 27 70 75 62  6c 69 63 6b 65 79 2c 70  3···'publickey,p
(271)   10   61 73 73 77 6f 72 64 2c  6b 65 79 62 6f 61 72 64  assword,keyboard
(272)   20   2d 69 6e 74 65 72 61 63  74 69 76 65 00           -interactive·
(273) Authentication algorithms offered (%=unrecognized, *=disabled):
(274) 	* publickey
(275) 	% password
(276) 	  keyboard-interactive

A USERAUTH_FAILURE (with partial success = false) showing a list of
methods.  Since it's the first list of userauth methods I get, and I
asked my client print it, it does.

(277) Out data (60):
(278)    0   32 00 00 00 05 6d 6f 75  73 65 00 00 00 0e 73 73  2····mouse····ss
(279)   10   68 2d 63 6f 6e 6e 65 63  74 69 6f 6e 00 00 00 14  h-connection····
(280)   20   6b 65 79 62 6f 61 72 64  2d 69 6e 74 65 72 61 63  keyboard-interac
(281)   30   74 69 76 65 00 00 00 00  00 00 00 00              tive········

My USERAUTH_REQUEST, trying to start keyboard-interactive.  Both the
language tag and the submethods string are zero-length.

(282) In data (45):
(283)    0   33 00 00 00 27 70 75 62  6c 69 63 6b 65 79 2c 70  3···'publickey,p
(284)   10   61 73 73 77 6f 72 64 2c  6b 65 79 62 6f 61 72 64  assword,keyboard
(285)   20   2d 69 6e 74 65 72 61 63  74 69 76 65 00           -interactive·

A USERAUTH_FAILURE listing keyboard-interactive as a useful
authentication method to try, even though it just failed!

What's broken here?  Am I confused about something, or is the server
just weirded out?  And in any case, what's the Right Thing to do in
response to something like this?  transport-24 is not clear on what it
means to receive a USERAUTH_FAILURE like this, one which lists the very
authentication method it just failed.

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse%rodents.montreal.qc.ca@localhost
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B