Does voip.ms handle storage of voice messaging on their own servers or is that something you have to provision yourself?
It's their server entirely. I've configured things so that voice messages are also emailed to me, just in case their server
loses them later. I don't know much about their voicemail server --
it's not exactly boldly advertised -- other than that it appears to work.

Messages remain on their server (even if also emailed) until deleted from the handset
(or presumably from the web interface which I have yet to explore).
There's gotta be a downside somewhere, but I haven't found it yet. Some people complain about the Customer Service reps being in Mexico when one dials in to them, but the online chat reps have french names..
There are also a few complaints about slow porting of existing DIDs, but I think that's probably a rampant industry-wide issue here in Canada.
Note that your incoming-calls (DID) provider doesn't have to be the same as your
outgoing call server..

Cheers