Internal Instant Messaging solutions

Hi All

We have a large public sector organisation containing over 15'000 users, I am looking for a solution to private Internal Instant Messaging.

Historically we were looking at adding this to our internal Exchange 2003 service, however now we have moved to a Windows 2008 R2 domain which all users are a member, we do have an Exchange 2010 appliance but only 3000 of the 15000 users are on this, the remainder are on a goverment provided central email service accessed via RPC over HTTPS.

Are there any products (Microsoft preferably however other vendors if needed) that would provide us with an AD based instant messaging solution.

Ideally it would use there AD account as we would not want to create a seperate DB of usernames and "fake" email address just for the instant messaging to work.

Thanks