NCO loses lock after a while for certain values of alpha
I will assume that your PLL is purely digital. Is that correct?

I assume your PLL consists of 3 blocks

The first block calculates the phase of your incoming signal (the signal you wanna lock to).

The second one will compare the phase of the signal to the phase of your "internal oscillator" yielding the error e[n]

The third one is your "controller" which I assume is some kind of PI controller with alpha being the proportionnal gain and beta being the integral gain. 

Your phase detection algorithm that detects the phase of your input signal has some kind of low-pass effect. This creates some kind of delay between the output your PI controller and the measurement. This delay puts a limitation on the values of your alpha and beta parameters. I.e. if you increase the values too much, your PLL can be unstable and you will lose the lock.

If you change the phase of your incoming signal, how many samples does it take for the change to be effective? This will tell you approximately what your delay is. From this delay, you should be able to find alpha and beta gains that will give you a good gain and phase margin. You should try at least 6 dB and 45 degrees.

edit : How you obtain the value y*? Is is some kind of delay chain? Hilbert Filter? I assume there is some kind of delay involved...

edit 2 : Your controller seems ok, your gains are low. Your bandwidth is low and thus the closed-loop should be stable. I suspect that your error happens when the phase measured by algorithm transitions between pi and - pi. Picture this case

Phase NCO = (pi - 0.001)

Phase ref = (pi + 0.001)

The phase difference should be 0.002 radian right?

However, phase ref will not actually be (pi + 0.001) but rather (- pi + 0.001)

Yielding error = (-2*pi + 0.002). Which is not the real error, this has the effect of suddenly increasing the bandwidth of your controller, which is something you do not want to do. This is probably why it is stable at lower values of alpha. The glitch would be there but not as big. 

I'm assuming your algorithm yields a phase between -pi and pi, if the algorithm yields a phase between 0 and 2*pi, the thinking remains the same.