If you don't need it to go to the recycle bin, you can do a Shift-Delete which just deletes the files without sending to the recycle bin, and seems to be a bit faster, especially with lots of little files. (Might just be my imagination, though)
Otherwise, I have heard that regularly emptying and/or reducing the size of your recycle bin can help.
If you don't mind the command line, you can use DEL, or better yet use Cygwin if you are comfortable with Linux commands.
But yeah, I agree, it can be a huge pain, especially when working over a network.
[EDIT]
Googleing around, I just found a suggestion that turning off indexing can help as well.