The UC Bell: About the dreaded 504 timeout error with Lync Push Notifications (rings a bell?)

Like several others, I was pestered with issue where at a customer site, Lync 2013 Push notifications to Apple and Windows Phone failed to work despite the apparently correct configuration. The error was 504 timeout, which is thrown out by the push notification test cmdlet:

Test-CsMcxPushNotification -AccessEdgeFqdn

(where -AccessEdgeFQDN is the internal Edge Pool FQDN).

Alas, this is a frequent although (fortunately) well-documented issue on a number of great blogs with several possible (and working) resolutions. Worth nothing reminding proper Push Notification functionality is dependent on
But what happens if everything else fails and you still get stuck with it?
After some further research and attempts, the only quick fix for me was to break federation and re-create from scratch like follows:

1) remove federation with push.lync.com
2) remove federated provider for LyncOnline
3) disable push notifications
Set-CsPushNotificationConfiguration -EnableApplePushNotificationService $False -EnableMicrosoftPushNotificationService $False

3) add back Lync Online hosting provider:
New-CsHostingProvider -Identity "LyncOnline" -Enabled $True -ProxyFqdn "sipfed.online.lync.com" -VerificationLevel UseSourceVerification

4) add back allowed federated domain for Push Notifications:
New-CsAllowedDomain -Identity "push.lync.com"

5) Re-enable push notifications:
Set-CsPushNotificationConfiguration -EnableApplePushNotificationService $True -EnableMicrosoftPushNotificationService $True

6) Worth checking that Federation is enabled:

Set-CsAccessEdgeConfiguration -AllowFederatedUsers $True

Tested again, and, happy days :)