I didn't know about the CSS img border trick there. 'Twill come in very useful.
Also, before you just get rid of img borders entirely, try experimenting with making the link color one the agress with the rest of your design and altering the width. A one or two pixel border can look very nice in an image gallery or such. If you want to use the CSS way (and now that I know it exists, I would too recommend it) and also have images in a menu or such that you don't want borders around, use class definitions to switch between images with borders and ones without.
On an alternate note, do you really think that by this time web users are dependent on having an underline to define a link? As long as you use an easily distinguishable color (after running it though one of the various color-blindness tests to check that way too) and don't use switch the mouse icon from the default pointing finger, I should think that the users would be able to figure it out. I guess it depends on your audience, though. If yours is a business site or some such, having underlines might be best as a 'just-in-case' type thing.
Comment/Reply (w/o sign-up)