This is strange for when you use the cleanup function all but the latest restore point should get removed.
There are three other options for you:
1) Disable and re-enable system restore, this will at first instance delete all restore points. Re-enabling it is important for if anything fails it will mean you have to reinstall the system (as no restore points are left)
2) Decrease the allowed disk space for system restore (also, if it has already exceeded the allowed disk space something strange is going on)
3) Like you are already stating, reinstalling will give you a clean copy of windows without the useless disk filling. But usually formatting the drive is not really required for creating some extra space
As to point 1, disabling system restore works in the following way:
1) Open control panel
2) Go to the view with all the icons (nog the category view, but the one which will show much more icons)
3) Click on 'system'
4) On the left click on 'system protection'
<now you see all your drives and in the list it says if protection is on or off
5) Select your C drive and click on 'configure'
6) You can now choose to disable this system protection
<after disabling the system protection all restore points should be removed>
--> You can also press the delete button in the lower right corner of this window. This will keep the system protection on but will delete all current restore points and settings meaning your system volume information gets reduced to zero. This does mean it will at some point create a new restore point.
As to point 2, at the place where you can disable system restore you can also set the maximum allowed space for system restore
As to point 3, to create more room I would not recommend reinstalling your entire system. However, reinstalling the entire system is my preferred way of fixing things when a system goes haywire. I am assuming the C drive is your SSD, copy the files you need to backup to a different drive then the C drive and then reinstall windows. During the installation you should be able to select the option to fully format the C drive and install windows there. After the installation you should have a fully functioning system with your files saved on the other drives. Make sure you have external backups of critical files, photographs etcetera you do not want to lose if something fails.
But before you even consider point 3 which, like I said, seems overkill for this situation. When in the window where you can disable system restore, it says how much room system restore is using. What does it say over there? There is a line which should say something like 'current usage x,xx GB'.
Because 19 GB of system volume information on a 35 GB disk seems strange. Generally I would say max 2 GB on a 35 GB disk.