Linux – cp and cat on Centos 5.5/ext3 is 10x slower for files in certain directories

I was sorting some large files (91GB across 27 files) with GNU sort when I noticed that iostat -dxk 3 showed very slow read speeds, between 5 MB/s and 10 MB/s, with 100% disk utilization. I tried cat large-file > /dev/null, and got similar performance, only slightly higher. The same for cp large-file /tmp/, with /tmp on a separate disk. vim experiences the same, as well as scripts I write in Ruby reading files, if that helps. Write speed is fine and fast though.

EDIT: It looks like these operations are only slow on files in a certain directory. The same operations on other files in a sibling directory (same disk partition), end up being fast, with above 90 MBPS read speed. This makes no sense to me. Could it possibly be due to the manner in which these files were constructed? I created them by reading in a lot of other files, and writing each line into an appropriate "bucket file", depending on the first character in the line (so a-z, and a single file for others). So I was pretty much simultaneously appending lines to 27 files, one at a time, through 8 processes while reading a couple thousand files. Could this cause the sequential order the blocks representing a file to be out of order instead? Hence the slow sequential reads afterwards?

However, I tried using fio to measure sequential read performance, and it clocked in at 73 MB/s. Also notable is that my boss got proper read speeds when downloading some files via FTP from the same machine.

So I'm guessing this is some configuration issue somewhere, but I have no idea where. What could the reason be and how can I try to fix it?

Edit: This machine is running under Citrix Xen virtualization.

Edit: Output of iostat -dxk while sort is loading a large file into its buffer (get similar output for cat/cp):

Device:         rrqm/s   wrqm/s   r/s   w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
xvdb              0.00     0.00 1000.00  0.00  6138.61     0.00    12.28    24.66   24.10   0.99  99.41
xvdb1             0.00     0.00 1000.00  0.00  6138.61     0.00    12.28    24.66   24.10   0.99  99.41
xvda              0.00     0.00  0.00  0.00     0.00     0.00     0.00     0.00    0.00   0.00   0.00
xvda1             0.00     0.00  0.00  0.00     0.00     0.00     0.00     0.00    0.00   0.00   0.00

Edit: Further performance degradation after a few hours (with breaks for the disk when sort was processing). It almost looks like random IO, but there's only a single sort operation going on, with no other processes doing any IO, so reads should be sequential =/ :

Device:         rrqm/s   wrqm/s   r/s   w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
xvdb              0.00     0.00 638.00  0.00  2966.67     0.00     9.30    25.89   40.62   1.57 100.00

Device:         rrqm/s   wrqm/s   r/s   w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
xvdb              0.33     0.00 574.67  0.00  2613.33     0.00     9.10    27.82   47.55   1.74 100.00 

Device:         rrqm/s   wrqm/s   r/s   w/s    rkB/s    wkB/s avgrq-sz avgqu-sz   await  svctm  %util
xvdb              0.00     0.00 444.33  0.00  1801.33     0.00     8.11    28.41   65.27   2.25 100.00