I know there is a URI scheme that can open Microsoft Teams, such as msteams://MY_PATH.
Now, how can I use this URI scheme to open a new conversation with a specific contact, given the contact email?
Bonus question: is there any way I can also attach a message to the newly created conversation? I don't need this message to be sent, but only to fill the message field in the newly created conversation.
Yes, it's definitely possible to do this using Deep Links. In particular see Deep linking to a chat. In particular, it says:
You can create deep links to private chats between users by specifying the set of participants. If a chat doesn't exist with the specified participants, the link will navigate the user to an empty new chat.
I don't think you can send an attachment directly, as the conversation doesn't actually exist until the first message is posted (per the link: "New chats will be created in draft state until the user sends the first message"). Perhaps there is an alternative though - you can pre-create the first message in a draft state (see the optional "message" parameter) and you could insert a link to a file stored in the Team's SharePoint document store / OneDrive / other.
Example URL:
https://teams.microsoft.com/l/chat/0/0?users=<user1>,<user2>,...&topicName=<chat name>&message=<precanned text>