BackTweets is a very useful service that searches for a URL in the major URL shortening services on Twitter.
Their bookmarklet takes over the current window and away from the content you want to search twitter for. My version below will open a search in a new window or tab preserving the original page.
When you are on a page that you want to see if it has been twittered or tweeted already, just hit the bookmark and a new window will open with the BackTweets search.
javascript:(function(){ window.open('http://backtweets.com/search?q='+encodeURIComponent(location.href)); })();
Just drag this link to your bookmark toolbar: