Иногда, если регулярное выражение составлено неправильно или плохо, время выполнения метода может быть очень долгим. 

Как-нибудь можно ограничить его по какому-нибудь параметру? По времени или по количеству рекурсий?

А разве дотнетовский движок поддерживает рекурсивные регекспы?

Вообще существуют условные конструкции, но не думаю, что из них можно что-то подобное вытащить. Скорее всего тут надо вместо метода Matches использовать Match и вытягивать по одному соответствию, а все ограничения вводить в коде(имхо).

Я имел в виду неотъемлемую рекурсивность "регекспов". Система же пытается то так, то сяк сопоставить, а при неудаче возвращается на исходные позиции. Вполне можно написать выражение, которое будет перебираться очень долго. 

Мне надо именно Matches. Хотел быстренько написать регексп-дебаггер, да вот завис на этом интересном вопросе. 

Как это так, нельзя ограничить время выполнения метода? Может, есть какой-нибудь инвоук для этого?

Сейчас делаю поток, который можно будет убивать.

При помощи Match можно реализовать ту же функциональность. Среди перегрузок этого метода есть такая, в которой можно указать с какого индекса начинать просмотр строки. То есть найдя соответствие можно при следующем вызове идти дальше. В промежутках можно проверять любые условия и при необходимости остановить просмотр. 
А на счёт встроенных возможностей я сомневаюсь.

Заменив Matches на Match, мы понизим время в N раз. А там рост экспоненциальный. То есть, выигрыш будет сомнительный.

Это надо проверять опытным путём. С регекспами так навскидку ничего сказать нельзя.