How can I do a regex search and replace in a VBA excel macro?

Since you are trying to replace a format, I'd do a replace based on a format. With a regex it seems like you'd be forced to deal with the underlying number.

I tested this in XL 2003 and 2010:

Sub ReplaceByFormat()
With ActiveSheet.Cells
    .Replace What:="", Replacement:="=cell(""filename"")&cell(""Address"")", _
             SearchFormat:=True, _
             ReplaceFormat:=False, _
             LookAt:=xlPart, SearchOrder:=xlByRows, MatchCase:=False
    Application.FindFormat.NumberFormat = "h:mm AM/PM"
End With
End Sub

EDIT

First off I had a mistake above in placing the FindFormat at the end. It needs to be at the beginning (Doh).

There is no OR argument to the replace function. So below, I've just repeated the code for a second type of format.

This code assumes that the dates are all constants. If they are formulas you could fix with a find and replace in the vba. If they're a mix, you'll need to extend the code a bit:

Sub ReplaceByFormat()

With ActiveSheet.Cells.SpecialCells(xlCellTypeConstants)
    Application.FindFormat.NumberFormat = "h:mm AM/PM"
    .Replace What:="", Replacement:="=cell(""filename"")&cell(""Address"")", _
             SearchFormat:=True, _
             ReplaceFormat:=False, _
             LookAt:=xlPart, SearchOrder:=xlByRows, MatchCase:=False
    Application.FindFormat.NumberFormat = "m/d/yyyy"
    .Replace What:="", Replacement:="=cell(""filename"")&cell(""Address"")", _
             SearchFormat:=True, _
             ReplaceFormat:=False, _
             LookAt:=xlPart, SearchOrder:=xlByRows, MatchCase:=False
End With
End Sub

Firstly, a better pattern would be:

  /[0-2]?[0-9]:[0-5][0-9]:[0-5][0-9] [A|P]M/

Secondly, the actual code without anything specific to your problem would be as simple as (adapting to your scenario, off course):

Set RegExp= CreateObject("VBScript.RegExp")
RegExp.Pattern = "[0-2]?[0-9]:[0-5][0-9]:[0-5][0-9] [A|P]M"
For i = ......
  Expr = Format(ActiveSheet.Cells(i, 1).Value, ActiveSheet.Cells(i, 1).NumberFormat)
  If RegExp.Test(Expr) Then Replace....
Next i

This way VBA will treat the values in the cells as they appear.

EDIT

About the pattern also matching "29:00:00 |M" - I'm not sure why "|" is considered a valid char since it means "OR". The same happens if you use ",". Anyway, a better one surely is:

/^(([0-1]?[0-9])|(2[0-4])):[0-5][0-9]:[0-5][0-9] [A|P]M$/

• Allows 0-24 hours only
• "^" and "$" makes sure the cell contains only time format value in it, denoting begining and end of the string

But in the end, it doesn't matter if the RegExp pattern matches EXACTLY only time values, because the formating of the input data will be done with Excel, wich will pre-validate the cell content (if you type "29:00:00" it will convert it to 5 AM of the next day). This being an Excel solution can lead to an Excel solution only, but not a global solution.

In that sense, using regular expression is not even common in Excel - RegExp is a string tester, without semantic meaning evaluation, for which you have other means to validate inputs in this context. For instance, you could do the same with pure VBA:

Function IsTime(rng As Range) As Boolean
  Dim sValue As String
  sValue = rng.Cells(1).Text
  On Error Resume Next
  IsTime = IsDate(TimeValue(sValue))
  On Error GoTo 0
End Function
'Source: http://excel.tips.net/T003292_Checking_for_Time_Input.html