Don’t use GoDaddy though. I was searching for a domain on that site and after a few minutes it was taken.

There are reasons to avoid GoDaddy, but what you experienced isn’t really a GoDaddy-specific problem. If a domain gets registered on one provider, it will be unavailable on all providers. Unless you are accusing them of falsely saying they were taken but are available for purchase at a premium. I don’t think I’ve heard of them doing that, but who knows what kind of greedy tactics corporations will try these days.