> But then you have to balance that with the overhead of supporting an "old" feature for the sake of old users.

That's the thing actually - supporting the old behavior in case of FF3 wunderbar is trivial as it's just a subset of the new behavior. Just restrict latter as this:

  (a) search for a match only among the URLs
  (b) match at the head of the URLs; skip "www." when matching if it's present

I'm not an FF dev, but this should hardly take more than a couple of hours of work, esp. if one is familiar with the code.