Nevermind... it looks like SmartyNames isn't reliably detecting which domains are free. I've made a search where it showed many "free" domains which ended up non-free.
That probably means they are either not issuing DNS queries or GoDaddy is really evil.