Drupal - 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
  ->delete('key_value')
  ->condition('collection', 'update_fetch_task')
  ->execute();