Your advice is fantastic as per usual. The array of arrays does make a lot more sense, suggestion #3 makes even more than the current stuff. I'll try both to get a better feel how each performs, and try and be a little more clever next time. Thanks :).
Bioinformatics
Comment on Re^2: A more efficient sort or heap algorithm...
You could also take a look at how GFF files are stored in Bio::DB::GFF or Bio::DB::SeqFeature::Store which use RDMS to handle these types of range queries (mysql,postgres, sqlite) and an in-memory berkeleydb implementation.
The get_features_by_location is basically what you'd want to use for your problem.