I had similar behavior when played with zero crossing detection. The reason was that the zero crossing signal was very wide, in range of 0.5ms.
So it you use falling edge detection your timing is off by 200us and at minimum voltage setting the triac trigger goes to beginning of next half cycle.
Another problem with falling edge was that sometimes I got false signal from raising edge oscillation.
Best results I got with raising edge (debouncing applied) and 200us correction for timing.
Also, you could limit the delays to 500us - 9500us range, I don't see any use for values smaller or higher.