Have you found any better resolution to this problem yet? I'm having the same issue. I generate all my elements with CGI, but I don't generate them in the same order that I print them. I'm considering setting all tabindex's to 0 which would effectively disable it.
Actually, I put together a patch and sent it to Lincoln Stein. Once he saw the problem I was having, he proceeded to come up with a much better solution. He's since released it to CPAN.
So if you get the new version of CGI (change log version 3.12), you'll notice that the tabindex behavior is now an option and the old behavior (no tabindex) is the default again. That should fix the problem. I've tested the new code, but haven't moved it through our system to production yet.