Got my car back from the Service Center tonight after they fixed my front USB ports (a cable wasn't seated somewhere), fixed a misaligned piece on the drive stalk and looked at my phone as a key issue.The only thing I haven't tried is to factory reset my phone. I'm getting close to trying that if the SC doesn't figure it out.
While I was there, they walked through a number of potential issues that can be had with a phone as a key. Things like ultra power saving mode, airplane mode, bluetooth on, app running, app has GPS access, app has bluetooth access, and a few others I don't remember. While I was explaining my situation where the the Phone Key would show "disconnected" I showed the advisor my phone, as he was looking at it, the phone started to connect to the car. It has never done this before after saying "disconnected". This is progress! I unlocked the car manually to show that that worked as well. While we talked a bit longer, it disconnected again and I showed him so he said lets go out to the car. We got up and started walking to the door and my Phone Key connected again. (BTW, the car was about 50 ft away the whole time.) As we approached the car, the car locked since I had unlocked it earlier. I was able to touch the door handles and it unlocked successfully... Wow! And the car started on the first try.
Note that I didn't get the new update (2018.12) while at the SC and am still on 2018.10.5. The one thing that did happen that may have fixed it is last night at 4am, my ZTE phone received a very unusual android update to Android security patch level February 5, 2018. Wife got this update as well and her phone is working too.
At this point, it looks to have been fixed by the Android update. In other words I got lucky since I haven't had an update for over 6 months on my phone.