This fails for extensions without Search Tools (com_weblinks, com_tags, 3rd parties) where it results in a double All entry.
The reason however is not in a buggy Search Tools, but in a buggy JHtmlContentLanguage::existing(). See https://github.com/joomla/joomla-cms/blob/master/libraries/cms/html/contentlanguage.php#L42
Here we create some sort of caching. Since Search Tools is using this function with $all = false and $all is only considered during the first lookup, all subsequent calls will return without the All entry.

The solution is to move the if ($all) part out of the cached database query.

This worked for me:

    public static function existing($all = false, $translate = false)
    {
        if (empty(static::$items))
        {
            // Get the database object and a new query object.
            $db    = JFactory::getDbo();
            $query = $db->getQuery(true);

            // Build the query.
            $query->select('a.lang_code AS value, a.title AS text, a.title_native')
                ->from('#__languages AS a')
                ->where('a.published >= 0')
                ->order('a.title');

            // Set the query and load the options.
            $db->setQuery($query);
            static::$items = $db->loadObjectList();
        }
        if ($all)
        {
            $all_option = array(new JObject(array('value' => '*', 'text' => $translate ? JText::alt('JALL', 'language') : 'JALL_LANGUAGE')));
            return array_merge($all_option, static::$items);
        }
        else
        {
            return static::$items;
        }
    }

Since the currently used array_unshift modifies the existing static::$items, it is no longer usable for us. Thus I came up with this solution instead. If there is a better solution, feel free to adjust as needed.

Nice @Bakual!

I will close this issue and if you have time please open another with your code! Thanks again!