Found an issue on Github that solved my problem.
Turns out an Exchange contact's (first) EmailAddress has an hidden PidLidEmail1OriginalDisplayName in addition to its address.
When you set the email address to an invalid one, the invalid address is stored in the OriginalDisplayName and its address is cleared, which is the reason the contact's email address is (Empty) in Office 365 People's contact list but the invalid address seems to still be there when you edit the contact.
PidLidEmail1OriginalDisplayName is an MAPI property. In order to obtain it, we need to use extended properties. The request should look like below but with the spaces URL-encoded to %20:
GET /me/contacts/{id}?$expand=singleValueExtendedProperties($filter=id eq 'String {00062004-0000-0000-C000-000000000046} Id 0x8084')
The response should include an additional field containing the invalid address:
"singleValueExtendedProperties": [
{
"id": "String {00062004-0000-0000-c000-000000000046} Id 0x8084",
"value": "user@example?com"
}
If the contact has multiple email addresses, use PidLidEmail2OriginalDisplayName/PidLidEmail3OriginalDisplayName for the contact's second or third email address.