Actual cause and solution
After much research I finally found out what's causing the issue. There was an entry in Event Log saying
The speed of processor 0 in group 0 is being limited by system firmware. The processor has been in this reduced performance state for XY seconds since the last report.
This led me to the actual cause, which is: critical battery level.
When battery level is critical, CPU underclocks itself to save energy. When battery level is back to reasonable level, CPU spins up to 3GHz as it's supposed to.
What misled me was that when I put the PC to sleep and woke it up again it was fixed. This was actually caused by the fact, that the brief sleep allowed the battery to charge above the critical treshold.
Relevant answer on Superuser
Old answer for reference:
I actually come up with a solution. It seems that for one reason or another Windows thinks that the "normal" power state is the power state that's supposed to be lowest possible.
That is probably why turning on and off does not help, because there is no power state change in between.
What actually helped was instead of restarting to use sleep. That way the computer switched to the C3 sleep state and by waking up something got switched back to where it was supposed to be. The frequencies are back to 3.3GHz :)
Update: It happened again and sleep did not help. Restart didn't help either. I need to do the whole power cycle. Completely shutdown the computer and then turn it back on. That fixed it.