First the picture was set wrong in both Outlook and Lync 2010. I used CodeTwo Active Directory Photos to remove and readd the picture which fixed the problem in Outlook.
I tried to remove c:\users\username\appdata\local\microsoft\communicator\sip_%username%@domain\galcontacts.db and galcontacts.db.idx which didn't update anything (except recreate the cache files).
Note: The same user has issues with the GAL taking extremely long to update.