There is probably an impossibility theory somewhere for two clients generating ordered ID without communicating with each other. What if one client was travelling near the speed of light for example? It isn't obvious what order would be correct since the two clients would have wildly different perceptions of time.
Yes, it’s impossible in theory. Same as the two generals problem, if I’m not mistaken.
If they're generated on the client you would need to keep clock drift[0] in mind since the leading bits are time based.