SSD suddenly extremely slow (50x slower)

Solution 1:

So, the final answer is a bit embarrassing, as I should have been able to figure it out, but I was looking in the wrong place. The crucial clue was in the question regarding the speed of the HDD -- tests indicated that it had slowed down as well.

My class that handles reading the data on disk has a default read size for its internal buffers. When doing random access this should be relatively small, because you aren't going to use any of the buffered data later. When performing operations across the full file sequentially, larger values give better performance because you will re-use the data. Given that this was a constant in a piece of shared code, tuning for one application using the code essentially broke the tuning for random access, thus causing the massive slowdown I was experiencing.