Which keys are you deleting and which ones remain?
Some keys are copies of others, you may just be deleting the copies. Next time you log in / reboot the copies are recreated from the "masters".
Can you post full details of one example. In regedit, Export all the "Shell / Open" keys for a specific program. Edit the exported files using Notepad and and copy and post the key data here?
Tip:
Whenever I Export keys from the Registry, I always rename the exported file to a .txt file straight away (keeping the .reg part of the name). That way if I double-click it it opens in Notepad rather than is applied to the Registry. Seems much safer to me.