Cannot update: "No available releases found"
Solution 1: SQL Query

While checking updates Drupal creates some rows inside the key_value table which should be deleted after checking is complete but looks like they doesn't for some reason. So deleting the related rows manually solved my problem:

DELETE FROM key_value WHERE collection = 'update_fetch_task';


Solution 2: hook_update_N()

If it is not possible to execute SQL queries via MySQL CLI on your server, then you might want to create a hook_update_N() in a custom module:

$database = \Drupal::database();
$database
  -&gt;delete('key_value')
  -&gt;condition('collection', 'update_fetch_task')
  -&gt;execute();