I've checked and done everything you've said, but I couldn't find anything wrong... It was still the same.
So I decided to start from the ground up and I made a new layout which would use the other half of the IC.
Now some things have changed, but it's still not working. But I do think I managed to narrow it down somewhat.
When I first connect the powersupply I get a zero at Q2. In this state I get 0,55 volts at the C2/C3 junction (with or without the relay) . Than when I press the button,Q2 becomes 9 volts and I measure 8.1 volts at the C2/C3 junction (again with or without the relay). And this is where it stops working properly. Pressing it again, I do hear the relay switch, but Q2 remains high and after this, the button doesn't do anything anymore. I do get a response over R2 every time I press the button.
Now here's something I find interesting: When Q2 is high and I disconnect the power, the voltage start dropping slowly. If I press the button, it discharges faster, but only for a brief moment. So if I press and release it a couple of times, it takes 15-20 seconds to fully discharge. Now if I reconnect the power, Q2 remains zero and the cycle is finished.
I have to mention that I have tested with 2 different IC's and they both act the same.