Okay, I found the cause of the discrepancy. In Xenial, all 4 MySQL packages are marked as manually installed.
So I’d have to supply all the 4 corresponding MariaDB packages on the command line manually, too, for them to override the MySQL ones.
@BanzaiMan I could make a workaround PR so that MariaDB addon starts working in Xenial+ before https://github.com/travis-ci/travis-cookbooks/pull/1057 is deployed.
But I would rather help you resolve whatever problem you are having with updating VM images – it has prevented a timely apply of quite a few bugfixes already.