I'm currently using this method and it works perfectly:
public static void CreateEmailInDefaultMailEditor(string to, string subject, string body)
public static void CreateEmailInOutlook(string to, string subject, string body)
Thank you for the answers & comments.
Here a small update to the question and probably the solution (I'm still not completely sure what the problem was): I could reproduce the problem to every computers of my department I tested (and not just two as mentioned in my question). After a few days, I noticed that everything was working again. I didn't change the code of my program nor did I deactivate the anti-virus.
What I didn't mentioned in my question (I thought it was not important), is that all computers were new. And I think it could be the problem: Windows has an Index Service, and I can imagine that at the beginning, it could take some days until the whole computer has been scanned. Searching for the default mail manager can in this case take long time, but as soon as the Indexing Service has done his job, searching for the default mail manager is fast again.