When you insert in sorted order into a b-tree (as you do with timestamps), later inserts will be more likely to be all in one block, and also more likely to be near the top of the tree.
Since b-trees have the guarantee that no root-to-leaf path is more than a constant factor longer than any other, you are probably hitting the very edge of that constant, and since disk seeks are the designated hitter of the performance team, you're getting hit pretty hard.
So, effectively, even your index is growing fragmented the more you use it.
To verify the fact that you're not hitting the data file though, maybe you could strace it and watch for reads on the index and the data file.
Typically, one expects a b-tree lookup to require at most 1 disk seek (for the leaf-nodes), and ideally your indices are fully in memory. So, color me skeptical that fragmentation of the index itself is to blame here.
One of the primary virtues of b-trees is that they make efficient use of disk. Even if the full data structure is too large to fit in memory, because of the large branching factor you can usually fit all the interior nodes in memory. So, in a lookup, only the final access of the leaf node requires a disk access. Of course, traversal may require additional seeks and reads.
Since b-trees have the guarantee that no root-to-leaf path is more than a constant factor longer than any other, you are probably hitting the very edge of that constant, and since disk seeks are the designated hitter of the performance team, you're getting hit pretty hard.
So, effectively, even your index is growing fragmented the more you use it.
To verify the fact that you're not hitting the data file though, maybe you could strace it and watch for reads on the index and the data file.