My company has a similar size, and we have a self-hosted Mattermost instance. We're switching away because the executives bought into another product but that's a different story, Mattermost works well at that size.

self hosting. having some growing pains performance wise with it due to election / end of year change freezes. ouch