Auto cleanup querystore not working
A few days ago I updated the server to SQL Server 2016 SP2 and the problem disappeared. Now when the querystore hits 90% it is cleaned up till it reaches 80%.

I don't know if SP2 was the solution or was it the restart of the SQL Service due to the update.