Correction, your theme was still compliant with XHTML 1.1 and CSS 2.1, but the plug-ins you added injected additional code that wasn’t compliant.
Unfortunately, there’s no easy way to maintain compliance if you’re using plug-ins. The best you can do is validate your theme and all of the markup you are personally responsible for, then hope that other developers have taken the time to validate their own work.
The alternative is a lot more work on your part – you can still use the core functionality of the plug-ins, but don’t allow them to output any markup to the browser. Add your own custom layer that unhooks everything the plug-in touches, and build your own output buffer. This is the only way you will have control over the style of markup being sent to the browser.
Several plug-ins are beginning to use HTML 5 … others are trying to use CSS3. If you install these plug-ins and don’t take steps to sanitize and validate their output, then your site will cease to validate properly.