Even if you're deduplicating commits / data internally, you can tell that that commit is not present in that repo as it is not an ancestor to any ref in that repository.

(You might argue that determining what refs contain a commit is potentially expensive, perhaps, but GitHub already does this, so I'd argue that it's not that expensive.)

Then it should be possible to store the originating repo along with the commit so that commits aren't visible in a given "repo" until they are pushed or pulled into that repo

Good thing Github is allowed to associate data with a commit ID, like they already do with rebased commits, as noted in the subsequent sentence.

github doesnt use plain bare repositories for their repo hosting, so they can do whatever they deem useful :)

if they did you'd be spot on though