Боюсь, что RegExps не подходят для вашего варианта использования, так как они будут менее удобны в обслуживании и медленнее, чем более прямой подход, такой как:
Function AllInStr(str As String, tokens() As String) As Boolean
AllInStr = True
Dim token As Variant
For Each token In tokens
AllInStr = AllInStr And InStr(str, token) <> 0
If Not AllInStr Then Exit Function
Next
End Function
Проверено в этом тестовом примере:
Sub test()
Dim tokens() As String
tokens = Split("{0} {1} {2}")
Debug.Assert AllInStr("{0}{1}{2}", tokens)
Debug.Assert AllInStr("{1}{0}{2}", tokens)
Debug.Assert AllInStr("{1}{0}{2}{2}", tokens)
Debug.Assert AllInStr("foo{1}bar{0}blah{2}", tokens)
Debug.Assert Not AllInStr("foo{2}bar{0}blah{2}", tokens)
Debug.Assert Not AllInStr("foo{2}bar{0}blah{12}", tokens)
End Sub