I find that when deleting a connection profile, it will sometimes come back. Also, when uninstalling Pulse Secure, even though I do not check the "retain profile information" it keeps it anyway and puts my old connection profiles into Pulse Secure when opened. I want to permanently delete connection profiles when I press the little X and it asks me if I want to delete the connection. Yes means yes.
What version of PCS are you using? Do you have a cluster? Are you seeing connections you added still on the Pulse client _or_ the ones that are pushed down from the appliance when you login and start Pulse?
I would recommend opening a case with support so we can investigate further.