Certainly a useful service. I know this because the way I used to accomplish this earlier was, create a Google customized search and manually enter the sites that I bookmarked with delicious and search from there.

So you got that covered, and I will use it.

However, I just signed up and imported all my delicious bookmarks and did a search for a tag and the results were not so impressive. Only 5 with historious and 17 on delicious. Hopefully this will get better.

Looking forward to using your service. Good job!