~1000 Mailbox's and a Windows solution. While zimbra and google are good, I'm going to give Microsoft this one.
Exchange & Windows server are built for each other. I've seen an Exchange 2000 server still running on Windows 2000 server up until mid '09... It was only replaced because they wanted to use all the new bells and whistles in Outlook 2007!
So for that volume of users, go Exchange. Server 2008 R2 is a fantastic server OS, and Exchange 2007 will do wonders!
Things to consider with exchange: I'm going to assume that they are already running an active directory environment? Are all users located in the 1 building or spread across several... if several, what is the bandwidth like? All the users will need to use Outlook... Exchange does, however, have a nice Outlook Web Access client.
Exchange works of a MAPI protocol, so if 1000 people have outlook open, that 1000 open connections to your exchange server... make sure exchange has it's own server, and plenty of CPU and memory, not to mention storage!
Whats the budget like for this too? Licensing will be the biggest cost for exchange (next to the hardware).