During the migration to Office365 we've prepared many computers with Office2007 installed.
Some of them could connect to Office365 immediately and others not.
Because we've had set gpo's for Outlook settings and autodiscover worked properly it was hard to find what caused the problem.
Problem - authentication
The problem was with authentication. Problematic Outlook's didn't have anonymous option in the security settings on connections tab.
Solution - Microsoft Updates
Outlooks which caused problems were set to NOT get Microsoft Updates.
After check the option to automatically get updates in Outlook settings and install them - anonymous option was in place and profiles has been configured properly.