I've submitted my outlook add-in 6 times now and every time the certification failed for a different reason. The last rejection reason I got was that my add-in didn't work on Office 2013 and Office 2016 (which they also refer to as O365 Perpetual).
I develop on a Mac and I have no idea how to go about debugging why my add-in is not working on those older Offices. Can't I just drop support for older Office suites? How could I test these environments?
I'm pretty close to quitting and just not publishing my outlook addin. I have never experienced a worse app review process.
If you want to be published on the Office Store, you need to support all the platforms for the minimum Outlook API Requirement Set in your manifest.
If you do not need to support Outlook 2013 or Outlook 2016, you can set your minimum API requirement set to 1.5, which will drop support for those versions (1.4 was the last version supported by those versions of Outlook). When you submit to the Office Store, please make a note that your minimum API set means that the add-in will not run in those Office clients.