For a long time, I used a freeware utility called Columbine Bookmark Merge. I don't know if it has been updated in a while and it only does part of what you want (It doesn't do link checking).

Also, while this utility will handle Netscape 4.x, I couldn't find any utility that handles Mozilla, Opera or Knoqueror. To my dismay, Mozilla bookmarks now seem all bound up in some sort of XML format and I see very little sign of utilities that deal with it (I had a heck of a time trying to find info on the bookmark format, period).