Lets assume you want to store a valid date.  I'll further assume that you'll want to do Date things on that date (either in SQL or in code or somewhere, but you probably want to use it).

Religious tool fanatics will say “regex is the only way to go”.  It might be, but I think there is a much nicer way to do this.  Use the language's (of your choice) built in tools, or write a custom method to do this for you.

I'd do something like this:

public bool IsDate(string date)
{
 DateTime dt;
 bool isDate = true; //assume tbDate.Text is a date
 try
 {
  dt = DateTime.Parse(date);
 }
 catch (FormatException efx)
 {
  //failed, so not a date.
  isDate = false;
 }
 catch (ArgumentOutOfRangeException aoex)
 {
  // failed, so not a date.
  isDate = false;
 }
 return isDate;
}

Use that function in a custom validator, or put it in a utility class and use it all the time.  It works for a wide variety of formats, as shown by this impromptu test:

string[] dates = new string [] { 
  "4/4/2003","4/4/03","May 4, 2003", "4 May 2003", "2003-04-04", 
  "4/41/2003","14/4/03","Masy 4, 2003", "4 Maya 2003", "20023-04-04" 
  };
 foreach (string date in dates)
 {
  bool isDate = IsDate(date);
  litResults.Text += date + " => ";
  if (isDate)
   litResults.Text += " Valid Date
\n";
  else
   litResults.Text += " Invalid Date
\n";
 }

Generating the following output:

4/4/2003 => Valid Date
4/4/03 => Valid Date
May 4, 2003 => Valid Date
4 May 2003 => Valid Date
2003-04-04 => Valid Date
4/41/2003 => Invalid Date
14/4/03 => Invalid Date
Masy 4, 2003 => Invalid Date
4 Maya 2003 => Invalid Date
20023-04-04 => Invalid Date

Just trying to check within a single format is difficult enough with regex, trying to accept all those formats would give anyone a headache.  You also win by doing this in code if your language of choice supports localization.

No, every post won't be about avoiding regex, I just have to get a few things off my chest.  Remember my grain of salt.  It's all about the right tool for the right job.