Here is a patch which implements Matthew's suggestion. It significant slow down the use of locale-sensitive regular expressions, there is a possibility for race condition between compiling and matching, and it doesn't solve the issue for explicitly cached expressions. Also I prefer that matching depends on locale at the time of matching, not at the time of compiling.

This patch can be considered as nonperfect solution for 3.4 and 2.7. But for 3.5 I'll try to implement better solution.

Microbenchmark:
$ ./python -m timeit -s 'import re' -- 're.match(br"\w+", b"abc", re.L)'

Before patch: 100000 loops, best of 3: 10.4 usec per loop

After patch: 10000 loops, best of 3: 37.5 usec per loop