Yup I have had the same dilemas - when I run my dropped doamin campaigns and think I have found a beauty - I go to register it "alls good" and it's "available" .... so I go through check out and then get the dreaded "Domain is already Registered" we'll try again or issue a refund ..... DoH!
I almost got a big fine when buying my first domain, and accidentally clicked one of those "Include This" buttons. But other than that, there a great company to buy from.