WhatsApp MessageService is always killed shortly after exiting the app
I've been having exactly the same issue as yours. I can also see that the MessageService service is being killed after around 10 minutes. After the service is killed, messages are only received when opening the app. While googling today for this problem, coincidentally found this thread which you had posted just 3 hours ago.

I'm using a new phone on which I installed Cyanogenmod 13. I've already tried to change several settings related to battery usage, memory optimization etc., but to no avail.

I've started using this phone 2 days ago and the whatsapp issue has been happening since then. Tomorrow I'll try to uninstall and reinstall whatsapp from the Play Store, since this one was restored from a Titanium Backup backup. I saw in a forum someone who resolved a similar issue by doing that... he also had restored from a TiBu backup and was having such problem.

By the way, your theory about GCM seems to point to the right direction - in my wife's phone the MessageService service is also killed after around 10 minutes, however, she doesn't have any delays in receiving whatsapp messages - so maybe it indeed relies on GCM for that.

Let me know if you make any progress on the investigation or come to a solution. Let me also know if I can help you with anything else.