Support

You have identified the problem correctly. It's closely related to one of the Joomla extensions updates bugs I have discussed in https://www.akeeba.com/news/1746-working-around-joomla-s-broken-extensions-updater.html Let me quote the exact passage:

Each extension can have one of more update sites. The update sites are XML files hosted publicly on the web. Their location is defined in the XML manifest file of each extension per https://docs.joomla.org/Manifest_files#Update_servers 

When you install or update an extension (note that installing an update and installing an extension afresh uses the same code in Joomla), Joomla inserts or replaces records in the #__update_sites table for the extension it is installing. This is done through the extension/joomla plugin’s (plgExtensionJoomla) onExtensionAfterInstall event handler, see https://github.com/joomla/joomla-cms/commit/05cdddafe2eccb335a757080c4035a4419090fa9 By the way this is why disabling this plugin breaks extension updates and the reason why have a workaround in our software to install missing update sites manually (i.e. in case you unpublished this critically important plugin!).

There a couple of problems with Joomla's approach.

If the Installer - Joomla plugin is unpublished the update sites records are not updated when you install or update an extension. If it' published, the lack or error handling may lead to the update sites being duplicated. Visiting the Control Panel of our software will address this issue since we are running some custom code. However, there was a bug between 8.0.1 and 8.0.3 (inclusive) which prevented that code from running in our software.

If you uninstall the extensions (components, plugins, modules, ...) of a package extension before you uninstall the package extension Joomla may fail to uninstall the package extension; trying to reinstall the package extension would give it a new extension ID which means that now you have two sets for update sites simultaneously active: the old one which can't be removed or replaced automatically and the new one. Since both update sites try to retrieve updates for the same extensions only one will "win". If it's the one with the empty extra_query or the one with the extra_query that contains an old / invalid Download ID your updates will fail. In the latter case since there is a dlid in the URL our own installer plugins won't kick in.

To cut a long story short, there is no "easy" fix. That said, the fix will be permanent.

Go to Extensions, Manage, Update Sites and delete all update sites which reference a URL in the cdn.akeebabackup.com domain. DO NOT delete the ones which reference the akeeba.com domain name.

ONLY FOR Akeeba Backup 8.0.1 TO 8.0.3: Then go to Akeeba Backup, Options and remove your Download ID (use cut to save it to your clipboard). Click on Save & Close. You'll now be asked to enter the Download ID. Paste it and click the button to apply it. This forces our custom code which handles the update sites to kick in and make sure the update site is correct and references the correct Download ID.

Make sure the Installer – Akeeba Backup plugin is enabled.

Now go to Extensions, Manage, Update. Click Clear All then click on Find Updates. The updates should be installable now.

This should be a permanent fix. The leftover update sites from older versions are removed. The only one remaining has the correct Download ID. The component's options also have the correct Download ID. Even if the update sites table "loses" the extra_query content again our installer plugin will see there's no dlid query string parameter in the download URL when Joomla tries to retrieve an update and add it.

Eventually, Joomla 4 will be released. With Joomla 4 you will no longer need to enter the download ID in the component itself (this option will be removed from Akeeba Backup 9 which will only be compatible with Joomla 4). Joomla 4 gives you the option to enter the Download ID directly in the update site management and handles the extra_query by itself using information we pass in our extension's XML manifest. The custom code we have will greatly be simplified into checking if the update site exists and is correct, as well as that you have entered a Download ID. The update site management and the download ID management will be handled by Joomla itself.