[Riim]

Тем более жутко, что нет вообще никакой необходимости replace-ить все текстовые ноды без разбора (на кой ляд это делается?).

Если не хотите приводить свой код, то хоть объясните подробней, как вы предполагаете это сделать, а я уж сам сделаю.

Можно один раз объявить, и записать свойством в функцию-коллбэк, иначе, они создаются каждый раз при вызове callback(I, i);.

А стоит так мучиться для одноразового кода. Разве, что ради идеи:

window.onload = function() {
	var callback = function(noda) {
		var v = noda.nodeValue.replace(/(http\:\/\/www\.youtube\.com\/watch\?v\=[0-9a-z]{11})/gi, '<a href="$1">$1</a>');
		if (v != noda.nodeValue) {
			var div = arguments.callee.div;
			div.innerHTML = v;
			if (div.firstChild) {
				var f = arguments.callee.fragment;
				do f.appendChild(div.firstChild);
				while (div.firstChild);
				noda.parentNode.replaceChild(f, noda);
			}
		}
	};
	callback.div = document.createElement('div');
	callback.fragment = document.createDocumentFragment();
	TextNode.each(callback);
};

Странно, что после строки "var f = arguments.callee.fragment;" не нужно отчищать этот самый фрагмент. Видимо после добавления в документ он сам очищается.