I get significant performance improvements compared to fetching the data every time for smaller sets of data but once the dataset reaches a certain size (approximately 3 $data_id's and 7500 $applicant_id's) the performance degenerates horribly.

Could Storable be switching from the C to the Perl implementation at that boundary? That would explain a sudden dropoff in speed.

Even without understanding the C code, it shoud be possible to figure out which implementation is being used when benchmarking.