2016 update

It’s been over 4 years since this question was posted and things progressed quite a bit.

You can’t use:

var els = document.getElementsByTagName("a[href="http://domain.example"]");

but what you can use is:

var els = document.querySelectorAll("a[href="http://domain.example"]");

(Note: see below for browser support)

which would make the code from your question work exactly as you expect:

for (var i = 0, l = els.length; i < l; i++) {
  var el = els[i];
  el.innerHTML = el.innerHTML.replace(/link1/gi, 'dead link');
}

You can even use selectors like a[href^='http://domain.example'] if you want all links that start with 'http://domain.example':

var els = document.querySelectorAll("a[href^='http://domain.example']");

for (var i = 0, l = els.length; i < l; i++) {
  var el = els[i];
  el.innerHTML = el.innerHTML.replace(/link/gi, 'dead link');
}

See: DEMO

Browser support

The browser support according to Can I use as of June 2016
looks pretty good:

(See: http://caniuse.com/queryselector for up to date info)

There is no support in IE6 and IE7 but
IE6 is already dead
and IE7 soon will be with its 0.68% market share.

IE8 is over 7 years old and it partially supports querySelectorAll – by “partially” I mean that you can use CSS 2.1 selectors like [attr], [attr="val"], [attr~="val"], [attr|="bar"] and a small subset of CSS 3 selectors which luckily include:
[attr^=val], [attr$=val], and [attr*=val] so it seems that IE8 is fine with my examples above.

IE9, IE10 and IE11 all support querySelectorAll with no problems, as do Chrome, Firefox, Safari, Opera and all other major browser – both desktop and mobile.

In other words, it seems that we can safely start to use querySelectorAll in production.

More info

For more info, see:

• https://developer.mozilla.org/en-US/docs/Web/API/Document/querySelectorAll
• https://developer.mozilla.org/en-US/docs/Web/API/Document/querySelector
• http://caniuse.com/queryselector

See also this answer for the difference between querySelectorAll, querySelector, queryAll and query and when they were removed from the DOM specification.