I suggest you go back to your PC and check the contacts list there. I suspect you have the 1000+ addresses in your personal contacts, due to your mail client misconfiguration.

I have one Exchange account for work. There are dozens of contact lists maintained by the IT department and one personal list. I keep the personal one empty and never had any sync problem.