First thing to check with starting probs is spark plugs and leads. When were they last changed? Remove and regap the plugs if needed. Next does the car have a distributor with a rotor arm? If so check condition of both. Look for hairline cracks in distributor cap that could let damp in.
If all of those are ok then the next thing to check is fuel supply. As you say the fuel cleaner worked for a while i would replace the fuel filter then run some injector cleaner through the fuel system.
Also as it starts with air filter removed does the air filter need replacing as a dirty air filter won't help