It's not our phones.. same issue on my wife's Note 5, my S6 Edge+, my daughter's S5, my friends HTC... it's the Google app itself with the issue. It seems after the app gets killed in the background, it stops "always listening". If you go into the app, say "OK Google" then exit the app, and within a few minutes try again - it works. But after a while when the system kills the background process it stops listening.
I'm going to try exluding the app from the optimization in settings and see if that helps.. but I believe it is Google who needs to fix it.