Первое приведенное Вами правило — о сложных словах с начальной частью, заканчивающейся на согласную, поэтому к словам с частью вело оно не подходит. Второе было бы применимо, если бы часть вело присоединялась к слову, пишущемуся со строчной буквы, например: велогонки, велобаза, велоспорт, велотренажер. Если же нужно присоединить приставку или первую часть сложного слова к собственному имени, пишущемуся с прописной буквы, то нужно руководствоваться правилом координации. По нему правильно писать вело-Россия, вело-Уфа (аналогичные примеры из правила: спорт-Одесса, фото-Москва). К сожалению, без учета орфографического правила было зарегистрировано название общественного движения «ВелоРоссия».

Правило звучит так: дефис применяется при записи конструкций с однородными членами, имеющими общий конечный элемент, если все члены, кроме последнего, представлены только начальными элементами; такой дефис называют «висячим». Например: шарико- и роликоподшипники; лит- и изокружки; кино-, теле- и видеофильмы; не двух-, а трёхэтажный дом; не только англо- и франко-, но и русскоязычные тексты; как водо-, так и газоснабжение; до- или послеперестроечные процессы; либо теле-, либо радиопередача; обер- и унтер-офицеры. Как видно из примеров, употребление висячего дефиса не зависит от слитного или дефисного написания сложных слов.

См.: Правила русской орфографии и пунктуации. Полный академический справочник / Под ред. В. В. Лопатина. М., 2006. § 112.

Корректно слитное написание. Медиа... — первая часть сложных слов, пишется слитно. См. словарную фиксацию.

Написание через дефис ошибочное. Слова с первой частью авиа- пишутся слитно: авиадиспетчер.

Правильно: ж/д и авиакассы.

Первая часть сложных слов авиа... пишется слитно: авиаиндустрия.

Правильно слитное написание: авиаперелет.