the problem is that rsync uses the modification time and size of a file as a quick-reference to judge whether or not a file has changed. There is a more detailed and precise way to check whether files have changed and rsync supports that aswell, however if the modification time and size of a file defer in the first place, these "more detailed" checks are skipped and then rsync assumes the file has changed, hence tries to copy the whole file over.
Specifically when in a heterogeneous environment (Windows+Linux, ...) and when not working on local filesystems (i.e. when using SMB mounts/shares or other protocols), there is a slight possiblity, that the modification times are not passed through correctly between the rsync source and it's destination.
It may very well be that the modification times are rounded up or otherwise altered by OS and/or network protocol used and hence appear be different (even if just slightly, even if the local filesystem has the "correct" mtime).
Please check whether this may or may not be the case & test it via command line (if possible) and utilities like "stat" (Linux) or if absolutely necessary perl/python mini-programs, which output the exact modification time as propagated via the OS and local filesystem properties (ultimately bypassing any network protocols like Samba).
Example output for the "stat" utility under unix:
$ stat somefile.txt
Size: 1014 Blocks: 8 IO Block: 4096 regular file
Device: 805h/2053d Inode: 1448800 Links: 1
Access: (0644/-rw-r--r--) Uid: ( 0/ root) Gid: ( 0/ root)
Access: 2012-07-21 17:20:33.548997182 +0530
Modify: 2011-08-16 23:27:19.648480473 +0530
Change: 2011-08-16 23:27:19.648480473 +0530
It can't be that your rsync commands consistently take "16 minutes" or so. That doesn't make any sense. Usually, rsyncs are getting quicker the less the differences are before & after each run. Only scp will take a constant time every time you run it, depending on the copy volume. So that fact, plus the fact that you already ruled out compression & encryption (ssh) can be the performance bottle-neck really make me assume there may be something going on with the modification time comparisons.
I specifically had this case myself with Samba mounts from my Synology NAS.
However, whether that is also the case with you or not, I hope you find the real cause of your problem soon.