Do you have a meter?
As you know, the pin 3 output is digital so it should be either high or low. The LED should be either on or off. My guess is the power supply is sagging for whatever reason. What is your source of DC power to the circuit? Are you sure it's stable?
What I'd do next is leave the LED and 1K resistor connected to pin 3, but remove the 10K connection between pin 3 and the transistor-relay. The circuit will still toggle upon application of alternating switch closures except you'll only see the LED go on and off. You'll also be able to confirm the edge-triggering behavior of the the switches. That is, it's the initial switch closure that toggles the 555 output. Either or both switches can remain closed, or can release from closed-to-open without incident. Once you get the circuit working without the relay, it should be easy sailing...
As for the initial condition, the 0.01uF caps are initially discharged when power is first applied meaning the voltages at pins 2 and 4 are both at 0V simulating a momentary switch closure. In your case pin 2 is "winning" the race. If you absolutely must have a guaranteed known starting condition, there are simple workarounds but this is a separate issue.
