You should be able to do this without any downtime. Below is a short overview of the steps you should take.
First, setup your mailboxes on your LP account to mirror your current host.
Next, go into your mail config on your old server and have it relay mail to the new LP host. Mail will now be directed to the new LP hosting.
Finally, switch your MX records to point to the LP host. Any message that hit your old server will be forwarded to the new LP hosting. This will prevent lost mail in the case that a mail server has a stale record.