Miwitte,
I would go ahead and put the WAAS in a seperate VLAN. Go ahead and check the wccp return method and make sure that they don't have negotiated return on or something like that. They may be getting around the seperate vlan issue if they have waas configured to return traffic to the redirecting router encapsulated in GRE header.
Can you post a show tfo connection summary and show statistics tfo to this post. You will see the overload condition in the show stat tfo command if its occuring. How large of a unit are they using? Are they using a NM or an appliance for WAAS? Any VPN on that device?
What type of traffic are they trying to accelerate? If its CIFS related traffic they may need to setup some more configurations under file services before they get CIFS AO going on. Normally WAAS will give me 80%+ accel on ftp transfers. I use that as a baseline test along with www.speedtest.net :)