We had exactly the same thing, where we had 27 different ministries, each with their own mto.on.ca. Each ministry was the same. Part of the exercise we went through was to collapse down to a single e-mail address: @ontario.ca. We did that at the same time we took the seven or eight e-mail systems we had running. We actually collapsed it into a single Microsoft exchange instance and we all went to one address.
It's very difficult, from a mental perspective. Ministries like their little name on it, but eventually everybody accepted it.
Even things like name resolution cause huge problems, so when you've got two John Smiths, somebody has to be John.Smith and somebody has to be John.Smith1 or John.Smith2. It can cause all kinds of issues, just so you know, but it can be done.