The DELETE verb only works on Exchange 2003 SP1 - it will not work on any earlier version/service pack. CDOEX, CDO 1.21, Extended MAPI, etc can do this on Exchange 2000 or 2003.
One possible work-around is to read the message stream using a WebDAV GET, modify the stream to remove the attachment and then do a PUT to write it back. You will want to watch-out to be sure that you do not lose any custom properties which you have set.
Also, you may use an unsupported OWA command to delete the attachment with Exchange 2000 and 2003. To do this, send a POST and "?Cmd=editattach". Again, OWA commands such as this should be avoided since they may not work in future versions of Exchange.