Sorry, the CCleaner tool is for actual entries applications make on the same level as "new" by installed programs.
You are actually talking about the "New" submenu of the context menu,and it is handled the same way as the briefcase method above. Each item is based on the file extension (type) of the file that will be created.
So open the registry editor ...
... Microsoft Access Database ... delete ...
HKEY_CLASSES_ROOT\.accdb\Access.Application.14\ShellNew
... Contacts ... delete ...
HKEY_CLASSES_ROOT\.contact\ShellNew\command
... Microsoft Word Document ... delete ...
HKEY_CLASSES_ROOT\.docx\Word.Document.12\ShellNew
... Microsoft Powerpoint Presentation ... delete ...
HKEY_CLASSES_ROOT\.pptx\PowerPoint.Show.12\ShellNew
... Microsoft Publisher Document ... delete ...
HKEY_CLASSES_ROOT\.pub\Publisher.Document.14\ShellNew
... Microsoft Excel Worksheet ... delete ...
HKEY_CLASSES_ROOT\.xlsx\Excel.Sheet.12\ShellNew
IMPORTANT: Before deleting/changing to each section I suggest you first Export it, saving it with a descriptive name like AccessDB, contacts, etc. This way if it causes other unwanted side-effects you can run the exported reg file and it will restore your registry entries.
Note: The ##s in each path are probably different if you are not using Office 2010 like I am.