I've used tuckey's UrlRewriteFilter in small projects, but I'm hesitant to use such a thing in a production environment that could touch tens of thousands of paying customers (it feels kludge-y). Is it fine to use a rule-based rewriting engine in production, and what are some alternatives I could use for clean URLs?
Yes, it is fine. A lot of large sites are doing it, in one way or another.
We're using the UrlRewriteFilter by Tuckey in our production environment without any noticeable issues or performance downfalls. Our services are heavily used with more then 10k hits per sec.
If you're using UrlRewrite just to process RESTful URLs - think about switching to Spring 3.0 (http://blog.springsource.com/2009/03/08/rest-in-spring-3-mvc/).
Also, consider using JAX-RS but I have no extensive knowledge about it's performance vs Spring.
I've used URL rewriting in mid-scale sites (10-20k visitors/day) and have never found it to be a bottleneck. I haven't used the reqriter you mention so there's a chance it may prove problematic.
In general, unless you've got some REALLY convoluted rules, the overhead of rewriting is going to be negligible compared to say opening a database connection.
There are also benefits to the user in terms of usability/remembering URLs and (also friendly URLs seem to make users feel more confident). It's also nicer when you're digging through error logs :)