Even the popular registrars accept Bitcoin payments and offer free whois protection. All that is left is a temporary email address and not using your own IP.

I'd call that reasonably anonymous. Pay attention to the TLD, because it might be against ToS to register some of them anonymously (mostly ccTLDs). There's plenty that don't have such restrictions.