However, when I just try and look up one key, it reverts to the deprecated implementation, even if I try and give it a hint that I expect the return to be a Long!

Deprecation doesn't affect the overload resolution rules. The only exception is

Deprecated(HIDDEN)

which hides the deprecated member completely.