Thank you all for your replies.

I have solved the problem, although I do not know which is the real solving step.

In hopes that it will help someone, here is what I did:

I did the cold reset once before, but I remember that some devices do not reset well with just a power cycle and a reset button press, and memory corruption would occur. Thus I:
1) Reset the base settings via the phone menu
2) Do a cold reset
3) Do another cold reset as soon as the phone boots up
4) Reset the base settings via the phone menu
5) Do another cold reset
6) Do another cold reset as soon as the phone boots up
7) Reset the base settings via the phone menu
Hoping the repeated resets would fully reset the phone.

Next, I thought since the problem is with authentication problems, it could be my ultra-long extension password (20 characters long). Thus I shortened it to 8 characters.

And since my asterisk logs seem to tell that the phone is not responding to authentication requests it sends, I thought maybe its a NAT issue. My asterisk server is set to only respond to requests from my network domain (phone.***.com). However, since the phone is on the same network as the server, I decided to just enter the IP address into all the fields. I thought maybe that's the cause of the authentication issues. Thus I changed the registry address to my domain name.

That solved the authentication problem (I hope, its been almost two days) but audio does not work. Changing all the other IP addresses into my domain name does not help. Finally, I decided to use a public STUN server, and things worked.

The funny thing though is that now I can use either my domain name or IP address and it'll still work. I've actually tried the above changes (not together, separately) before but it didn't work, funny that it worked when I did all of them together.

Thus, I guess the fixing steps could either be:
1) The cold reset process
2) Changing the password length
3) Using a STUN server

The stuttering problem is also solved.

I know this is confusing, but I hope it helps someone.