Hi Beat Besmer! I would like to take your post as an opportunity to clarify this process a bit more for people new to Odoo, like me. Because as of today, Odoo still has some built-in modules that don't support record creation based on incoming e-mails.

I was trying to create Purchase Orders from e-mail messages, for example, but I was seeing log errors like this (/var/log/odoo - file: odoo-server):

17-11-21 02:00:01,390 1293  odoo.addons.fetchmail.models.fetchmail: start checking for new emails on imap server YOURSERVER
2017-11-21 02:00:04,191 1293 odoo.addons.mail.models.mail_thread: Routing mail from John Doe <john@somedomain.com> to PO <po_odoo@somedomain.com> with Message-Id <033BEAFA3A88314AAD1AF741D8A56C0E95DD2533@YOURSERVER>: fallback to model:purchase.order, thread_id:None, custom_values:None, uid:5
2017-11-21 02:00:04,288 1293 ERROR odoo.sql_db: bad query: b'INSERT INTO "purchase_order" ("id", "currency_id", [... LONG COLUNM LIST...]

ERROR: null value in column "partner_id" violates not-null constraint

So here is an example of a simple "message_new" method that you can use on an Odoo 10 installation, for Purchase Orders:

Edit the file /odoo/odoo-server/addons/purchase/models/purchase.py and add the following lines:

    @api.model
    def message_new(self, msg, custom_values=None):
        """ Overrides mail_thread message_new that is called by the mailgateway
            through message_process.
            This override updates the document according to the email.
        """
        # remove default author when going through the mail gateway. Indeed we
        # do not want to explicitly set user_id to False; however we do not
        # want the gateway user to be responsible if no other responsible is
        # found.
        if custom_values is None:
            custom_values = {}
        defaults = {
            'name': msg.get('subject') or _("No Subject"),
            'partner_id': msg.get('author_id')
        }
        defaults.update(custom_values)
        p_order = super(PurchaseOrder, self).message_new(msg, custom_values=defaults)
        return p_order

I don't believe there is a particular order, but make it between two other existing functions (defs).

This was adapted from other Odoo methods that do have a message_new implementation, and using tips from other posts.
I believe that you can change it to fit your needs with other modules as well.

After modifying this file and restarting Odoo's service (sudo service odoo-server restart) you can configure an incoming e-mail server and set the "Create New Record" to Purchase Order, for example.

This function above will set the sender as "partner" (partner_id), so keep in mind that the sender will have to be a valid user in Odoo (otherwise the record creation will still fail). Either that or you will need to elaborate more in order to create a new user on the fly, case it doesn't exist yet.

More about: 

Configuring e-mail server and alias domain: https://www.odoo.com/documentation/user/11.0/discuss/email_servers.html

More information about this issue (and a sample for Odoo 11): https://github.com/odoo/odoo/issues/6757