If you look in perl.c at the S_parse_body() function, you'll see the loop that checks for switches. There's no particular ordering required, at least for taint and baby taint.

However, if this function only sees a taint flag after you've already invoked perl and it's already processed command-line arguments, the too late for taint macro will take over and exit. As far as I can tell, however, this has absolutely nothing to do with the position of a taint switch within the shebang line and everything to do with when and how you invoke the interpreter.