Thank you everybody for helping me with forum troubleshooting. The problem has been found. It's memory limit. After a few years of use, 512MB RAM + 256MB swap is not enough anymore (I have some suspicions that swap does not kick in, but it's a topic for a different story).
If somebody searches, and no changes plugins, core, or hardware, and you do not have plugins that depend on external services - check if it's a memory issue.
