Собака оказалась зарыта нестандартным образом и это связано с совокупностью нескольких факторов, а именно:
- У меня был даунгрейднутый composer до 1 версии (это связано с тем, что, когда я начинал разработку Magento ещё не поддерживала Composer 2... И нет, это было не при царе Саламоне, а всего несколько месяцев назад)
- Пакеты, которые я пытался создать и выложить были добавлены только что, что привело к тому, что они недоступны из под Composer 1
Выглядит это следующим образом: Composer 1 осведомлён о существовании пакета, может его найти, получить в списке, пакет есть на сервере (тут апи общее). Однако, для получения подробной информации о пакете нужно использовать зависящее от версии апи. Для только что созданных пакетов запрос по старому апи возвращает 404... Поэтому composer не только не мог найти никакой версии, но и до конца не мог понять, существует у него пакет или нет.
Решил проблему вернувшись на вторую версию Composer.