I gather that what you are trying to achieve is to continue to use the Mitel phone system, but migrate voicemail functions to 3CX? To do so would require you set up a sip trunk between the Mitel and 3CX phone systems. Whether you can get help from 3CX or the forums to set this up is unknown. Obviously, we are not going to be able to help with the Mitel side of this effort.
Next, I would assume the phone calls would come into the Mitel system and then, when appropriate, calls would be forwarded across the sip trunk to an extension in 3CX. That implies inbound rules on 3CX that route calls to the appropriate extension. This will provide voicemail to email, transcriptions, etc. If you want people to be able to login and listen to voicemails, you will also need to build a route to extension 9999 (default voicemail system extension).
Regarding your question about sizing, this should be fairly straightforward based on the number of users and an estimate of how frequently multiple people are receiving voicemails at the same time. From 3CX's perspective, a call into the voicemail system (either to retrieve or save a voicemail) is 1 simultaneous call. So, figure out how many people will be in the voicemail system at the same time and that's the size of a 3CX server license needed (plus a little extra for good measure). As a wild guess, for 250-300 extensions, maybe a 16 simultaneous call license would be enough? Given the cost of voicemail on Mitel vs the cost of a small 3CX system, my assumption is that 3CX will be much more cost effective.
If I have described accurately what you are trying to accomplish, my guess is that it is possible to do. The biggest challenge will be getting the shared sip trunk to register between the two phone systems.
Having read your post title one more time... if the plan is to use a 3CX server hosted by 3CX, ... well.... you will have to ask them if they will support such a configuration. My guess is probably not.
