Note that the CPO guidlelines do not require that the vehicle was never in an accident, but must not have incurred damage to the unibody structure. See
http://www.bmwmotorsports.org/pdf/BM...guidelines.pdf on page 10 for more details.
Now if they lied to you and flat out told you that it was never in any accident then I would go back to them and ask for an explanation and compensation.