I don't think voltage fluctuation is the problem. it sounds like a lack of voltage is the issue. you have your relay triggered by the ACC circuit. the ACC circuit has no power during engine crank.
ACC has power when the key is in the ACC and RUN positions, and is not powered whe the key is in the START position.
IGN has power when the key is in the RUN and START positions, and is not powered when the key is in the ACC position.
sounds like you need your relay trigger to be powered in all 3 key positions. there are two ways you can do it: use 2 parallel relays with separate triggers, or use 1 relay with dual triggers (diode protected).