There is a schema update required to enable this if you're running 2003 DC's and have never updated the schema beyond that. I'm not sure exactly the versions, but we had all 2003 R2 DC's and it wasn't working. Worked with MS for what seemed like weeks and finally found a difference between their test environment and ours. All I had to do in the end was do the 2008 R2 forest/domain prep and the pictures magically appeared.
The parameter in question was in schema attribute "Picture" the "mAPIID" attribute should be "35998". In our older version of the schema is was "not set". Was advised not to update this manually but to instead do the prep.
We are running 100% on Exchange 2007 and it works great as long as Outlook can talk to AD (if Outlook is offline, you don't get pictures and there is no cache). With Exchange 2010 you get the offline capability using OAB.
We wrote some custom syncing code similar to above that pulls the pictures from our ID badge database and samples them down to 96x96.
Works great!