How can I theme the outgoing contact mail?
I was able to get Berdir's answer working in Drupal 8.1.0. But I had to do a number of things to get it going.


Install mailsystem, swiftmailer, contact_storage, and contact (core) modules
Setup a custom contact form, configure it and add fields as needed.
Configure swiftmailer message settings (/admin/config/swiftmailer/messages) to use HTML.
Configure swiftmailer transport settings (/admin/config/swiftmailer/transport) to preferred transport type
Configure mailsystem default mail system settings to use swiftmailer for both formatter and sender plugins. I assume you could also configure per module in the later section if you like, however I did not try it.
Under /admin/structure/display-modes/view add a new view mode for Contact message, setting it's namespace to mail. This is the view mode that will be used when sending the email (somewhere this is hardcoded from what I can tell).
If you want a pretty display of the Contact message nodes on the site then you will also want to create a full view mode and configure that too.
Configure your view modes under the custom contact form you created. The Display Suite module really allowed for customizing the markup with it's field templates made available in display suite extras.


Note, I also have Berdir's MessageViewBuilder override in a custom module but I am unsure it is any longer necessary. I have not attempted to remove it yet.