I don't know how manually are you removing custom menu but there is a scirpt given with SDK "RemoveCustomMenu.jsx" which can be run whenever need to remove custom menu.
It is not that I don't have code to remove a custom menu, I am wondering why I need to remove it in the first place? And that aside, is there a way to do it automatically when CS4 is closed. The code I have in the 'beforeQuit' handler for CS5.5 is (works like a charm but not in CS4):
var myMenu = app.menus.item('$ID/Main').submenus.item('My Menu');
You might have more success installing another startup script that removes the custom menu at startup.
I know this thread is REALLY old (please forgive the threadomancy), but it came up high in my search results when I was looking for a solution to this very problem. Well, I found a solution so I thought I'd post it here for posterity.
I'm using InDesign CS5.5 and I used a startup script to add a custom menu. After removing the script and restarting InDesign the menu was still visible (though unusable).
Here's how I fixed it (USE WITH CAUTION!):
I simply deleted this file:
C:\Users\[username]\AppData\Local\Adobe\InDesign\Version 7.5\en_GB\Caches\InDesign SavedData
Restarting InDesign showed the menu has gone, finally.
I hope helps someone looking for a solution to this problem.