That's strange, ok just to be clear, what about when you factory reset does your phone auto update from Google Play all the system apps and services...? If so roll back to factory versions for as many apps and services as you possibly can or/and better still disable Google Play from automatically updating apps when it first connects after factory reset...
However if it's still acting weird even before you update any apps then maybe you need to do the opposite and update all htc and Google services framework apps to the latest version.
If those two methods doesn't work then I'm at a loss... and it could be that you need to go down the root phone method...