ok, if you cannot remove records due to your audit requirements, i think it comes down to query tuning;
can you grab some execution plans, and see if any of the inserted into teh cdc tables might benefit from indexes, either on the main table, or maybe even the CDC tables themselves?(i've not bothered putting indexes on any of the automatically built cdc tables...they only receive inserts anyway).
I'm sure you are already looking at the usual suspects... SARGabile arguments, catch all queries, indexing.
Lowell