Датчик на маховике осматривали , протирали?
Реле топливного насоса проверяли?
Была такая же проблема, мучился на мегане несколько месяцев, имеено на холодную несколько раз надо было пытаться заводить...диагностика у официалов не дала результата и т.д....подсказал один человек почистить датчик на маховике ...к нему намагнитилась какая то стружка металлическая....
Протер тряпочкой и всего то делов

а при такой проблеме, после поворота ключа зажигания раздается громкий щелчок?
или поворот ключа - и тишина?
Просто похоже на мою теперешнюю проблему. Стартер прочистил, почистил контакты, слазил в предохранители, аккум еще не старый, а машина может на утро не завестись. Проблема проявляется вообще непредсказуемо.

Было подобное 1 раз за 3 года эксплуатации. Вечером все "ок", утром как отрубило. Сразу возникло ощущение, что топливо не подается. Завелся с трудом с подработкой педалью газа. После прогазовки все "ок", никаких намеков на проблему. ИМХО вода или посторонние фракции в топливе попадают в систему, на АЗС могли ливануть что угодно.