Removing Cert Server from AD
Have a look here: http://support.microsoft.com/kb/889250
I removed an Enterprise CA from an AD domain (Windows 2003) that I "inhertied" and started w/ a new Enterprise CA with no ill effects by following the directions in that article, then put in a fresh deployment that worked fine following. All-in-all, I felt it went very smoothly.
I would check your GPOs to make sure they arn't pushing an auto enrolment policy
User Settings -> Windows Settings -> Security -> Public Key Policies/AutoEnrollment policies