Already using this regularly (and it got a 5-star rating). I have one criticism:
You can't relocate the box that pops up, I'd like to either have an option to choose what corner it goes to, or even better, be able to drag it around.
The extension does HEAD requests by default, and occasionally you don't get accurate responses back from the server. You can change the request type to GET requests in the options screen (right click on extension icon -> options) to get more accurate (but slightly slower) results.
Yep, as it essentially visits all links on a page to check their availability.
However, you can add rel="nofollow" to links you don't want to check. You can also exclude entire domains and specific links by right-clicking on the extension icon and clicking on 'options'.