Essentially yes, they should be blocking US traffic, or at least not operating any servers in the US and not serving ads to anyone in the US. That would mean sticking to www.baidu.cn instead of registering www.baidu.com (with MarkMonitor.com, a US-based domain registration provider).
Would this be 'better' than censorship? A matter of opinion - I don't think it would be all that better and I am guessing you feel the same. But if you're using a US-style .com address, registering with a US domain registry, and serving ads to US visitors, then you're doing business in the US for legal purposes, and you become subject to US laws about how you do business - especially the laws that say you can't discriminate against people or infringe upon their civil rights. The concept in the US is that if you want to enjoy the freedoms and legal protections that go with being American, then you have to offer your services to others on the same basis that you expect to be served. You can't turn people away or give them inferior service just because you disapprove of them in some way such as not liking their gender, ethnicity, or national origin.
So if you're offering Chinese-language web search, in the US, and you're filtering the results in a way that limits the rights of US citizens/residents, then you're effectively discriminating against US residents who originally come from China. You can stop discriminating, or you can get out of the US market, but in the meantime you're liable to get sued. As I said, I really don't know if this is a viable legal argument or not, but winning the case is secondary to keeping the issue in the news.