Found a workaround
Okay, so I did a little digging and spotlight will find contacts on exchange that have been edited (note you will need 10.6.2). You must edit each contact individually. Click the edit button add a space to their name or some other piece of information. Save the change. If you added a space edit again and remove the space. if you added info that needs to be their you can leave it. This makes the contacts show up in spotlight. I know this is a pain if you have a bunch of contacts, but it is the only thing I have found that works.