Я не знаю почему срабатывает без индекса, но знаю почему не срабатывает для поля с индексом
SELECT @start AS oldsort, (@start:=testsort.sort) AS newsort from tablename AS testsort WHERE testsort.sort BETWEEN @start AND 39 ORDER BY testsort.sort DESC
При сравнении BETWEEN на первую строку попадает условие BETWEEN 37 AND 39, а на вторую BETWEEN 39 AND 39. И соответственно ничего не подпадает под это условие.
То есть что бы все срабатывало нужно BETWEEN 37 AND 39 или BETWEEN 37 AND @start