I never really fell in love with delicious (partly because I could never remember where to put the dots). I have, however, found a good bit of use out of Historious lately.

StavrosK is quick to mention it (he did in another Historious thread already), but I figured I'd give some endorsement for him. I like it (and I paid for a year).

The full-text search of the bookmarks (at the time you bookmarked them) is the key feature - it really does come in handy. It's also nice that it caches the text of those links as well.

Favbot will host your Delicious bookmarks for free

http://www.favbot.com/import-delicious.html

Me, too. Over 10,000 links. Welcome to the cloud.

Pinboard.in seems clean and simple.