Да, кстати, предполагается, что решение будет только с регулярками, без всяких callback-функций.

Есть один недочет. Не найдет такой код:

<nts:as asd jhg=321 asd:as=" ' asd:fake_attr " asd:as = ' " asd:fake_attr ' />

Но его легко поправить, поэтому я оставлю эту задачу для вас :)
Регулярка способна обработать за один раз - один тег. Без функции никак. Например с таким кодом можно:

string.replace(reg, function(){/* тут вся магия */});

Вот тут не понял, это что ещё за скобки и типы?

Ну ты сказал, что регулярками определишь вложенность тегов, скобки те же теги.

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

Понял.
Ну не просто выловить все теги, а ещё разобрать их на составляющие. Например, можно использовать для подсветки. Вложенность проверяется js-логикой, при нахождении очередного тега.

А чем плох простой?
UPD: понял, составляющие ещё нужны. Хотя проще, наверное, составляющие отдельно вытаскивать.

Ещё тем, что это найдет синтаксически сломанные теги. Получаются расхождения с парсерами браузеров. Хотя они тоже по-разному парсят, если синтаксис нарушен.
Ещё пятью регулярками и парой функций? Не думаю.

Пять простых регулярок лучше, чем одна сложная.

Простыми не получится. Например, твоя регулярка упадет на этом:

<!--
<div asdasas="">
-->

Комментарии не должны обрабатываться. Ещё есть инлайновые скрипты, стили, так что...

Пока ехал домой, мысленно нашел несколько багов, завтра исправлю.

Исправил баги:

/(?:<!--([\s\S]*?)-->)|(?:<!\[CDATA\[([\s\S]*?)\]\]>)|(?:<\/[\s\n\r]*([a-z\-_]+)(?::([a-z\-_]+))?[\s\n\r]*>)|(?:<[\s\n\r]*([a-z\-_]+)(?::([a-z\-_]+))?((?:[\s\n\r]+[a-z\-_]+(?::[a-z\-_]+)?[\s\n\r]*(?:=[\s\n\r]*(?:(?:"[^"]*")|(?:'[^']*')|(?:([^\s]+))))?)*)[\s\n\r]*(\/)?>)/gi

Сейчас всё должно быть тип топ. Только соответствующим образом нужно изменить регулярку по атрибутам.

А где может использоваться вся эта писанина?