While working on a recent Lync 2013 project, we faced an issue with the push notification which was not working as expected – some got the notifications, some not.
After reviewing all the configuration on Lync servers (front ends and edge) and found nothing, I found that the settings for Lync Online federated provider was set to Allow users to communicate only with people in their Contacts list and though ‘wait, the push service is an unknown people’ so let’s try by switching to Allow users to communicate with everyone using this provider.
Et voila, push notification starts working for everyone as expected.