Excel is your friend
We actually did something similar to kwbMitel's plan, migrating from a 1700-station SX2K to a Cisco Call Manager. Aside from major platform differences, the default Cisco phones that most users received were only 2-line instruments, so we had some rather long faces when users learned they were losing all of their personal speed call buttons. (Cisco's largest instrument is only 8 lines and comparatively expensive).
Still by exporting to spreadsheets we were able to capture all the personal speed calls & provide printouts to users, which was appreciated. The Cisco also accepts batch input from Excel, so as bad as it was, it could have been a lot worse. With some quality time spent with cut-n-paste we were able to put together some batch scripts for input that worked well.
TIP: limit your imports to 100 phones at a time else you'll have a lot of potential rework if you have something wrong someplace.
Fork-lifting the Octel Overture-250 and replacing with Cisco Unity Connection was even easier, as the new system was all LDAP-integrated. Once the phones were built & sync'd with LDAP, UUCXN was able to import them directly via the gui interface, though once more I recommend resisting temptation and only doing 50~100 at a time. Due to the platform differences our prep time for each batch of 100 averaged 3 days, so it was very important to keep departments together while making sure to have routes in both boxes to allow cross-platform calls (and prevent routes from looping).
Lessons learned, if we had it to do over, we should have moved the DID/DDI trunks first, because through platform idiosyncracies we lost inbound caller-ID when users moved to the Cisco and they didn't get it back until everyone was moved over (a 4 month project). Had we moved the trunks first, Mitel users would have lost CallerID but then regained it as soon as each was migrated. By moving the trunks last it initially gave the new system a black eye and we spent several hours explaining and then re-explaining to higher-ups what the issue was and why and when they could expect relief. They weren't very happy, but it was what it was.
Original MUG/NAMU Charter Member