For example I would expect them to have a keyserver hosting the public Keys of their customers and making sure that only the real customer is able to update his public Key. So nobody else can publish a public key for a given E-Mail without being the owner of the E-Mail.

An ideal implementation could be Web Key Directory (short WKD).

I did a quick search if mailbox.org supports WKD. It looks like mailbox.org Guard somehow supports it, but I never tried it. So maybe it is worth having a look at that.