Thanks for the input.
Maybe I did not describe the problem well enough. It was not only one device where the lookup email address resolution was not functioning, but all of them.
It appears that the active directory guys portaged a Domain Controller to some new hardware over the weekend and the BES was no longer able to access the appropriate group policies. After restarting the BES everything seemed to back in sync again and the lookup resolution is now fully functional.