"Какие пути решения проблемы? Купить соленоид с более сильным тяговым усилием (таковы есть в местных магазинах)" - более сильно-тянущий соленоид обычно соответственно потребляет и бОльший ток. А если учесть частые снижения бортового напряжения, то надо покупать соленоид на ещё мЕньшее напряжение сработки и, стало быть мЕньшее сопротивление, и, значит, ещё бОльший ток.
"натыкать в схему емкостей, которые в нужный момент обеспечат те 13-14V? Согласен, что это очень глупая идея" - это НЕ глупая, а оч популярная идея. СССР серийно выпускал магнитофоны с ЭлектроМагнитами, в которых мощность начальной сработки была в 4 раза больше мощности удержания. Начальная мощность как раз и обеспечивалась разрядом конденсатора большой ёмкости.
"который проходит через соленоид в момент открывания 5-7А" - современные малогабаритные
Ионисторы имеют оч малое внутреннее сопротивление и могут обеспечивать большой ток разряда.