Hi there,
this is basically just a shot in the dark but, I would suspect that the BETWEEN makes the optimizer do some curves where they are not optimal namely dissolving into two statements and not using the evidently right indexes.
I made these experience with slow queries using between, too.

Kind regards
Christian