Export PPT as mp4 or mov in PowerPoint
Sorry to answer this question myself. I had commented on a thread in Reddit who had a similar issue, and thanks to atomicshed, he linked me to another thread at Microsoft's site.
This solution worked for me:

Quit all Office 2016 apps
Rename the file /Library/Preferences/com.microsoft.office.licensingV2.plist to something else
Open any Office 2016 application, and sign in again to Activate the Subscription.


Now am able to export it as both MP4 and MOV. Thank you guys!