It sounds like similar symptoms to an air leak. Slightly rich idle mixture and add a bit more air and the revs rise.
Assuming the aux air valve lets extra air in on start-up and the connection removed is electrical, it sounds like it is letting air in when it shouldn't. Disconnecting the electrics putting it right suggests that something is erratically telling it to open when it shouldn't.
I am sure many would know more than me, but without their input, I suggest looking at whatever temperature sensor 'drives' the aux air valve. That might be the main coolant sensor, more probably one on the induction system. A dirty corroded connection would be nice to find?