This will be no help to you at all I am afraid but I had the exact same problem when fitting my Alpine head unit yesterday!!
I had Halfords supply and fit it (the £25 charge seemed quite reasonable for installation), plus I had a 10% off voucher from HotUKDeals ;)
Like you the guy could only wire up with it on permanent live and I was fuming at the time as my head unit doesn't have a face to turn it off and was constantly displaying the clock (even when the ignition was completely off
)
After I finished with the numpty from Halfords I went to Whitton Audio Centre where a professional promptly re-wired it and got it to work so that it is only on when the ignition is on
I don't know exactly what he did but on the invoice it says "Radio Ignition Feed Plus Re-install" if that helps.
An ICE expert will be along shortly so I wouldn't worry