This was a tricky one! So I tried to run composer update and it failed:
composer [ErrorException] Undefined index: extra
I ran it with -vvv and the dump suggested it was something to do with zaporylie/composer-drupal-optimizations, however, it wasn't.
I had a profile, but in composer.json I had this:
"extra": {
"installer-paths": {
"web/modules/contrib/{$name}": ["type:drupal-module"],
That's got drupal confused it knows modules exist and are enabled, the database shows this, but when we try and install stuff with composer its going to wrong place. Changed the path all worked great.