In French, "paying one's dues" spells "faire ses preuves", meaning, prove one's worth. That way no one is tricked into believing they owe anything to their employer. Sure, it's only an idiomatic phrasing, we don't think of the debt any more. Yet I'm sure it wasn't so at first, and I'm sure the idea lingers.

Like the Japanese saying "sumimasen" (forgive me, excuse me) to say "thank you" in some circumstances.