Problem: we publish sensitivity labels and they are viewable in OWA, but in Outlook and other Office apps the labels are not shown.

↑ We enable the Sensitivity button in the Outlook menu but it remains greyed out.

↑ In OWA we see that our labels are published successfully.
Additionally the labels are present if we install the legacy Azure Information Protection (AIP) add-in, but as that will be phased out there didn't seem much point in using this as a workaround.
Solution: in this case we found that although we had enabled the 'Information Protection for Office365 - Premium' we also needed to enable the 'Standard' feature alongside it.

↑ Both Information Protection features need to be enabled for O365 users.
References
Microsoft KB article
Microsoft - Sensitivity labels are missing in Outlook