So I disabled the module entirely with
bin/magento module:disable Magento_Braintree.
After that my checkout broke entirely with the error
Payment model name is not provided in config!. I debugged and found that
\Magento\Payment\Model\PaymentMethodList::getList still returns braintree methods as one of the payment methods:
Array (  => free  => substitution  => vault  => amazon_payment  => amazonlogin  => paypalpluscw_paypal  => paypalpluscw_paypalplus  => checkmo  => purchaseorder  => banktransfer  => cashondelivery  => paypal_express  => paypal_express_bml  => payflow_express  => payflow_express_bml  => payflowpro  => payflowpro_cc_vault  => paypal_billing_agreement  => payflow_link  => payflow_advanced  => hosted_pro  => m2epropayment  => braintree  => braintree_paypal  => aw_sarp_braintree_recurring  => aw_sarp_braintree_paypal_recurring )
I have cleaned the database from any remnants that contain the string "braintree". I also removed all the braintree settings in the
core_config_data table. Still the error persists.
I cleaned all caches, compiled di and so on... nothing helps.
Where does the list of payment methods come from if not from the database?