Joss, а какая необходимость использовать VBScript.RegExp? Это какие-то сложные шаблоны?
Если идти по пути условного форматирования, то в этом случае прийдется писать функцию в этом файле или в личной книге макросов. Это неудобно и наверняка тормоза (для 1000 ячеек поднимать 1000 экземпляров RegExp, к тому же неоднократно).
Вернемся к исходной задаче.

У вас для каждого условия в rst выполняется пробег по ячейкам диапазона (и так 20 раз). В плане скорострельности это плохой вариант. Лучше пробежать по диапазону 1 раз, а для каждой ячейки выполнить пробег по условиям в rst.
Присвоение фона каждой ячейке - тоже тормоза. Например:
Эта инструкция раскрасит фон трех независиміх ячеек. Поэтому, если не красить каждую ячейку, а собрать адреса в строку (в 20 соответств. строк, а потом скопом раскрасить - будет кошернее.
Адрес ячейки, это V0.Address(0,0)
Если есть доминирующий фон, то лучше сразу раскрасить весь диапазон, а затем менять там, где другое.