Улица – это улица, а проезд – это проезд. Сочетания типа улица Космический проезд, улица Славянский бульвар, улица проспект Мира неправильны, слово улица в них лишнее. Верно: проживающий в г. Воронеже, на Космическом проезде.

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

Правильно: проспект Металлургов.

Нормативны сокращения пр., просп. и пр-т (после этого сокращения точка не ставится).

Переименовывать ничего не надо, такие названия возможны.

Правильно без наращения согласно правилу написания дат: 25 октября, проспект 25 Октября.

Слова проспект, бульвар, улица принято ставить после согласованных определений: Океанский проспект, Славянский бульвар, Самокатная улица и т. д. Если же названия представляют собой несогласованные определения, то порядок слов иной: улица Льва Толстого, проспект Мира и т. п.  

Правильно: по адресу: проспект Мира, 235.

Нет такого правила пунктуации, которое требовало бы постановки в этом месте двоеточия. Но традиционно перед адресом двоеточие ставят.

В названиях улиц, площадей, проспектов и т. п. с прописной буквы пишутся все слова, кроме родовых терминов (т. е. самих слов улица, проспект, площадь  и т. п.) и слов года, лет. Что касается названий микрорайнов и пр., здесь действует такое правило: в составных географических названиях с прописной буквы пишутся слова, которые употребляются не в своем обычном значении. Правильно: улица Теплый Ключ, микрорайон Теплый Ключ (т. к. это не ключ, а район).