I'm almost tempted to call the first of these a bug:  isn't '((x|y)*)*'
a perfectly valid (albeit somewhat redundant) regular expression?  What
am I missing here?

Even if there are issues with capturing, shouldn't the version without
capturing subexpressions still work?

I get:

>>> re.compile(r'(?:(?:x|y)*)*')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/lib/python2.5/re.py", line 180, in compile
    return _compile(pattern, flags)
  File "/usr/lib/python2.5/re.py", line 233, in _compile
    raise error, v # invalid expression
sre_constants.error: nothing to repeat