FirefoxのtrunkにSelectors APIが搭載された！

function _$$(selector) $A(document.querySelectorAll(selector)); 
function $A(obj) Array.slice(obj);

_$$('a[href]');

こんな感じに動く。すごい。返り値がNodeListだからdocument.evaluateより使いやすいかもしれない。
関数名を$$ではなく_$$にしているのは、Firebug上で実行したときにFirebugにもとからあった関数をうまく上書きできないため。

Selectors APIについては IE8 で実装された Selectors API とは何か？ - IT戦記に詳しく載っている。
あと、Firefoxのほうは、:visitedも取得できるみたい。

_$$(':visited')