Why is ext3 so slow to delete large files

So it sounds like your real issue is you want to preserve owner and group settings, yet have the data migrated to a system that wants to map the settings to its own. You also want to keep the minimal-data-transfer setup that you get with rsync, but getting from "here" to "there" may take more time and effort than what you want to invest in. Tar would solve this problem but it takes the entire image of each file instead of the deltas.

To summarize: You want something that makes deltas of changed data, but preserves the attributes like tar, ignoring the destination system's user mappings (because there are no shared accounts).

Commercial Solution

The first (and probably not viable) option is to see if there is a backup client for the system you are using in Windows. For instance, Retrospect includes OS X and Linux clients that allow a Windows machine to back up the files with attributes attached. My work has used this arrangement for a couple of years, and with the exception of some I/O spikes client-side, it has worked as advertised. See if there is a client you can install on the Linux box that would allow you to "bridge the gap" between the two, and you won't have to worry about this. Note: I noticed you didn't post what kind of backup solution you're using, which means if you're using native Windows Backup (ick) you're out of luck.

Open-Source Solution

Here's something completely crazy: start a Samba server on the Linux side, put out a share for administrative use (hidden, set up for admins only, etc), map the share or use a UNC path on the Windows backup server, and then do a backup from the share. Yeah, your SIDs won't match, etc. (because there is no mapping between AD<->passwd) but that won't matter because Samba will do the translation for you, both during backup and restore. The downside is that you'll want to make regular backups of the Samba .tdb files to ensure you don't lose any settings, along with your user maps in /etc/passwd, etc. You'll also want to set up this share very carefully, as the wrong settings will cause the files to re-map to different values. The concept here is that we are turning Samba into a crude approximation of a "backup client" that can be accessed in a manner that is consistent with Windows. It also assumes that your backup software will take care of any delta/compression features you want...

Unlike the commercial solution, this has the added benefit of being able to work with the built-in Windows Backup, as the share appears to be just another Windows server UNC.

The second solution has already been mentioned by @Brent, and is worth looking into. This would be several steps up from the method I gave. Rather than plagiarize his post, go and read it instead.

Homegrown Solution

One solution would be to separate the metadata (ownership attributes) from the data, and transmit both to the server. Do to this, store the settings in a separate dot file, then transmit the dot file along with the contents. This would allow you to use rsync (if you so choose) while keeping the settings. As an added bonus, rsync will apply the same delta-transfer mechanism to the dotfile as well. During a restore, you would reverse the process by extracting the settings from your dot file and applying them to the directory contents. This is time-consuming, and wastes some disk space, yet it's simple (you have visibility of what is happening) and durable (it's just text files, so it's easily fixed), and simplicity sometimes is the easiest way, even if it seems "brute forced". I would choose this as your last option. Not only will you have race conditions (if you attempt to start the backup while the script is running, will the dotfiles be updated in time before they are backed up?) but you also need to craft everything by hand.

You would only need three scripts - one to regenerate the dotfiles in each directory for the settings, one to restore them, and one to clean out dotfiles when they are not wanted.

On generate/create: Store a dotfile in each directory that the dotfile belongs to. The dotfile essentially contains an ls -la so that the attributes are captured. Set the owner of the dotfile as root to keep mischief to a minimum. After processing that directory, have it go back and extract each directory from the dotfile (a simple grep will suffice) and then recursively go into each subdirectory by having the script call itself. When completed, the entire branch of the directory you started in will have all of the dotfiles in place for each directory. Run this script prior to the backup to "regenerate" and "refresh" your settings, or if possible, run it sequentially in-line with the backup script itself, to ensure that it completes before the backup starts.

On restore: The restore script would reset all dotfiles to correct ownership (again to keep out mischief), then recursively process the dotfiles in each directory, restoring your settings for each file. Each dotfile will require 3 passes, a pass for owner-group-world, a pass for naming the owner, and a pass for naming the group. File ops are usually not too bad so this should be very quick, baring very large directories with waaay-to-many files.

On cleanup: Simple, recurse each directory removing the dotfile.

Yes, it's an ugly hack. If I can find a better answer soon, I'll re-edit. Until then, it solves the problem.

Depends what you're doing exactly, but yes, ext file systems get slow when you've got a lot of files in one directory. Splitting the files into e.g. numbered subdirectories is one common way round this.