If I build a clean room implementation of some software, I have no patent problems. Right?

Wrong. Patents have nothing to do with implementation. Patents are about techniques, methods, underlying concepts. If two people independently come up with the same idea around the same time, the first to reach the patent office gains the right to charge the other licence fees. They can even prevent them from using the technique at all, at their own discretion. As long as the patent is written well enough that other parties cannot work around them, those parties are subject to the whim of the patent holder. The development of well documented clean room implementations is a way to deal with copyright issues. Following a legally protected path of reverse engineering is a way to deal with copyright and trade secret issues. Neither have any relevance to patent issues.