Version:           3.5.5 (using KDE 3.5.5, Debian Package 4:3.5.5a-1 (testing/unstable))
Compiler:          Target: i486-linux-gnu
OS:                Linux (i686) release 2.6.18

Im using tree view in the right pane and the folders sidebar
But i made the test with no sidebar and icon view in the right pane :

Reproducing the error
Go to a direcory where there is a samba directory mounted with all the persmissions (read write execute)(Test @ bash promt mkdir aaa && rmdir aaa works)
Create a dir (Right click create folder) named e.g. test
Descend into the dir( Double click on test)
Then go to the parent dir (that one containing test)
Select test. 
Press Shift+ Delete
Take "Could not remove folder sambamount/test"

Then Press Delete
Folder dissapears (seems deleted)
press F5
Folder Reappears

Summary:
Can not delete visited dirs from samba mount.