In the 6 years I've been running CCleaner on my XP SP3 system, rebooting, or stopping and starting "explorer.exe", is the only way to clear the run box entries. And I know of others who experience the same thing.
If you run CCleaner first, and then use "Task Manager" to stop and restart "explorer.exe" the box should clear without rebooting, although occasionally the "explorer.exe" entry you enter into Task Managers "File\New Task" box will remain in the run box window. And oddly enough, sometimes it doesn't.
I close down my PC every night, so rebooting is a normal thing and this minor issue doesn't bother me.
The check box does what it's supposed to do, but with at least some XP systems, the items aren't cleared until the computer is rebooted. I have a desktop and a laptop and this is the situation with both of them. A bug in some versions of XP probably.