In case it helps anyone with a similar problem, here is the closing summary from MS support.

Technical Summary : on one of your server, the observed EXECUTE permissions didn’t match the theoretical permissions set for a given login.

No reason was identified for this (DENY flags were checked at user, SQL group and Windows Group levels).

During the analysis it was noted that the TST1 Login mapped to the ‘PUBLIC’ DBUsername, which is unexpected (there should have been a TST1 username instead).

We also reproduced the problem outside the context of the application DB. The investigation perimeter had therefore become the SQL instance and the Windows AD context of the server.

We stopped the investigation before we could dive further on the ‘public’ login/user mapping.