Step 1: Login into portal.office365.com
Sign in with your Login ID and Password.
Step 2: When entering account click on Admin as shown into the picture.
Step 3: Click on the Exchange and a new window will open.
Step 4: In new window click on the Mail Flow.
Then click on the Message Trace
Step 5: Click on the Add Recipient section.
Step 6: After click on the Add recipient a new pop up window will appear on the screen now select one of the users and click on Ok button.
Step 7: Now click on the Search button and it will show all the messages.