I managed to solve this issue. It was due to my bad understanding of e-mailing in OpenERP. Note that, I had to switch from OpenERP 8 to OpenERP 7 due to some stability issues but I believe the process should be the same for both versions.

At first I tried to configure e-mail like any other e-mail client, which did not work. I configured my incoming email gateway and my outgoing e-mail server like explained above. The problem I faced was that I inserted one new config per user (with IMAP, SMTP) but I could not link it to a user. E-mails from maxime@deuse.me or from juliend@deuse.me didn't end in Maxime or Julien's inboxes. I kept getting the following error in my terminal: "create an appopriate mail.alias or force the destination model". 

In the end I never managed to force the destination model properly (the "Actions to Perform on Incoming Mails" tab) so I went with the appropriate mail.alias (Thanks Daniel for the suggestion).

This is how I proceeded:

To get the incoming e-mails

1. I went to my google account which manages the deuse.me domain. There I created a new user which I converted in a catchall e-mail adress.https://support.google.com/a/answer/33962?hl=en. This means that all e-mails send to any deuse.me address end up in this catchall@deuse.me inbox. Another solution if a catchall option isn't available would be to forward all your e-mail addresses towards the catchall@deuse.me address.
2. In the generals settings of OpenERP I set the Alias Domain to deuse.me
3. I set the ingoing e-mail server as the catchall@deuse.me address. I configured the IMAP config with this e-mail adress. "Server Action" and "Create New Records" should be left blank.
4. Once this is done users with the allias Maxime will get the e-mails from maxime@deuse.me and so on ...It works

To send e-mail

I did not configure the catchall adress as the outgoing e-mail server, otherwise all e-mails are send with the catchall@deuse.me address and only the name changes. When I did send an e-mail I wanted "Maxime Deuse <maxime@deuse.me>" to be the sender not "Maxime Deuse <catchall@deuse.me>". To achieve that Iinstalled Postfix mail server on my server and I kept the OpenERP outgoing mail server as localhost(configurations may be needed depending on your Postfix config). For this solution don't forget to set up spf records and DKIM's to avoid being marked as spam. (https://www.digitalocean.com/community/tutorials/how-to-install-and-configure-dkim-with-postfix-on-debian-wheezy)

I hope my explanation could help some of you who had the same issues I had.