I am using:
CuteEditor version 6.0
Safari 3.1 for PC or MAC
Firefox 2.0.0.13 for PC

I'm still having this issue.  IE7 is the only browswer that removes HTML when pasted correctly.  I used the following link to produce the screenshot below:

http://cutesoft.net/example/editor-onpaste.aspx