Inductor with high Q-Factor for low frequencies
do I just have to accept that for some physical reason Q-factors are
  always low in the sub-MHz range?


The value of Q factor is inductive reactance divided by series resistance and, given that the inductive reactance magnitude is \$\omega L\$ (or \$2\pi F L\$), at lower frequencies Q factor is necessarily smaller. If you need to understand the Q factor of a candidate inductor calculate \$2\pi F L\$ and divide it by series resistance of the coil.

But make sure that the operating frequency of the coil is below the coil's self resonant frequency (SRF). If you don't ensure this, you cannot regard the coil as having a "normal" Q factor.