If after all that it didnt get rid of the items you have to actually delete them from your registry for them to actually disappear.... on windows 2k its only in one place I am aware of....

BEWARE DONT EDIT THE REGISTRY UNLESS YOU HAVE BACKED IT UP AND KNOW WHAT YOU ARE DOING

HKLM>Software>Microsoft>Windows>Current Version>Run
delete the entries that you removed

In XP you have to also go to
HKLM>Software>Microsoft>Shared Tools>MSconfig>Startup reg
Delete the folders that you wanted to uncheck and no longer have run on startup or show up in your msconfig