Hopefully you are missing something. The Contact Form Solution was built with the Validation Toolkit... so it seems illogical to me as well that they wouldn't work well together. I suppose it is possible we have edited some code by hand that is causing a problem, but I'd need to know more about the precise cause of the problem to diagnose it better.
They should work together, and if they don't then we will treat that as a bug and address it. Please provide more details on what exactly you are trying to do and I can possibly provide more insight as to why the problem occurs.