Помогите пожалуйста построить регулярное выражение.

Есть строка с формулой Excel'я (например: "E1*A3+E1/A3")

Задача: Заменить все вхождения адресов ячеек ("E1", "A3") на сопоставленные им GUIDы в формате с фигурными скобками.
Например, если:
E1 = "{A31776AC-FA3F-E1E0-BFFC-F7CC6D569271}"
A3 = "{E165FCBD-E1D0-A358-9CA3-863A3E5AC196}"
должно получиться:

"{A31776AC-FA3F-E1E0-BFFC-F7CC6D569271}*{E165FCBD-E1D0-A358-9CA3-863A3E5AC196}+{A31776AC-FA3F-E1E0-BFFC-F7CC6D569271}/{E165FCBD-E1D0-A358-9CA3-863A3E5AC196}"

Обычный, последовательный, String.Replace не срабатывает, потому что GUID может содержать символы совпадающие с адресами ячеек. Поэтому выражение должно пропускать вхождения внутри фигурных скобок.

Язык реализации - Visual Basic 2005