Lollipop - Apps not autostarting
I was mistaken when I wrote that I have no task killers. It happened so that Lollipop has a built-in task killer feature called "Limited apps" that limits app execution in background. For some strange reason all SMS apps become limited by default. The feature can be found in settings under Applications item.