So I went ahead and investigated this - turns out you are absolutely right!
I did the following:
1. Created a dummy organization and a dummy repo, imported it to Gerrithub
2. Opened a few changes
3. Renamed the organization
4. Submitted the changes in Gerrithubs web UI
It all went off without a hitch.
So Github creates redirects for old org -> new org, but the organization name will not be reserved. Basically anyone can claim the previous organizations name and the redirects will be broken since they will then point to the new owners organization. At least that's what I get from reading
Githubs docs.
I suppose we then have to import the same repo, but from the new organization, into Gerrithub and deprecate/remove the old "repo". Slightly annoying that we will lose (or detach) the Gerrit review history, but not the end of the world. It's still in the normal git log after all.