The deleted certificate will be restored after rebooting. But why?
I had a possibly similar problem, related to a PPTP VPN and user certs.

Be sure to delete all old certificates from each keychain in Keychain Access. Also: be sure to choose "All Items" as the category.

In any case, I'm curious to hear whether you came up with a solution, so please remember to log any remarks on this page.