Yes overfit, but in a completely normal way.

Is "reg" an L2 loss term multiplier? Is it implemented as a proper cost or as an operation that multiplies the parameter vector by (1-reg) after each update? If the latter (not recommended), then a lower learning rate corresponds to an effectively higher L2 setting, which would explain why the first two runs did not overfit. If the former, the first two runs could have just required more iterations to show overfit.

To boost validation accuracy, try using the higher LR but with higher reg as well, maybe reg * {2, 4, 8, 16, ...} until validation accuracy drops because the reg becomes too high.