I just tested it using Pex for fun and - to my surprise - Pex was able to deal with regular expression and this AFAIK without any build-in knowledge of regular expressions.

  using System;
  using System.Text.RegularExpressions;

  public class Program
  {
    public static String Puzzle(String input)
    {
      if (new Regex("123(foo|bar){3}456[0-9]{5}789").IsMatch(input))
      {
        throw new ArgumentException();
      }
      else
      {
        return input;
      }
    }
  }

Pex reported three test cases.

  null                         ArgumentNullException
  ""                           okay
  "123foobarbar45600000789bb"  ArgumentException

Try this example yourself.

http://www.pexforfun.com/default.aspx?language=CSharp&co...

UPDATE: I was wrong - Rex was integrated into Pex in 2010 and this made Pex much smarter when it has to deal with regular expressions.

Rex is the equivalent of Pex (which is what this is based upon) for regular expressions: http://research.microsoft.com/en-us/projects/rex/

And more useful still if this worked on more than just portable class libraries [like the "original" Pex]