Это сложный вопрос. Наиболее надежный источник подобной информации - это различные отчеты путешественников (в основном авто-). Сайтов с ними великое множество и часто вполне достаточно вбить в поисковик что-то типа "дорога <один ключевой пункт> - <другой ключевой пункт>", чтобы получить вменяемый ответ на свой вопрос. Если речь идет о глухих регионах типа Карелии, Арх. области, где дорог немного и все они - так или иначе основные (неосновные там заканчиваются, как правило, тупиком), то существуют сайты, где информация об их состоянии систематизирована. Например - http://www.mccme.ru/putevod/Roads/roads10.html Конечно, порой она устаревшая, но практика показывает, что в большинстве случаев состояние дорог все-таки улучшается. И если 5 лет там был асфальт, то с 95% вероятностью он и сейчас там есть.
К сожалению, в средней полосе России подобные справочники покрывают лишь основные трассы, большинство из которых велосипедисту не слишком интересны. И тут выручают другие источники - например, на векторных картах "Дороги России" в некоторых областях асфальты и грейдеры обозначены по-разному. Еще один хороший источник информации - высокодетальные космоснимки. Очень часто по ним можно понять, что там за дорога, с довольно высокой степенью достоверности. Увы, но не со 100% - порой грейдер и старый асфальт различить проблематично, но если видны хотя бы признаки разметки - то это однозначно асфальт.