We are using CTEs in SQL Server (2008 pre R2), with a not too large object graph, and find the query performance inadequate for our realtime needs. We ended up flattening and caching graph representations in order to remove the bottleneck. The CTE query was the starting point to further queries throughout our applications so it benefitted all applications to introduce this layer.

Of course, then we had two problems on our hands. :)