Outlook discovers old server instead of Office 365 (Exchange Online) server

I deleted my old server with my Exchange server – I did not uninstall Exchange first, so I'm afraid that some stuff still floating around about my old exchange server.

We've moved to Exchange Online (Office 365), but when a client of mine tries to set up Outlook, it discovers my old server which doesn't exists anymore.

In ADSI I've deleted…

CN=Configuration,DC=DOMAIN,DC=LOCAL
CN=Services
-> CN=Microsoft Exchange
-> CN=Microsoft Exchange Autodiscover

And…

CN=Default naming context,DC=DOMAIN,DC=LOCAL
-> CN=Microsoft Exchange Security Groups

I'm not able to delete…

CN=Microsoft Exchange Security Objects

It gives me this error:

I've tried Google it, but has found a solution.

I've also deleted all DNS records of the server.

Questions:

1. How can I delete the Exchange Security Group?
2. How can make sure, my old Exchange server isn't discovered?

Thanks