... a) it only wants the keys, and thus is always called in scalar context, ...

Bingo :). If you think about it, what would FIRSTKEY or NEXTKEY return in a list context? There can only be one FIRSTKEY; and only one NEXTKEY at any given point. Each time either of these is called, you should return exactly one key. It is up to you to retain your position internally, and reset that position whenever FIRSTKEY is called.