Is this again for 4 billion vertices? Do the gremlin server logs show whether the problem is with the index or with the backend?
Does this occur for any vertex? Try to retrieve the first few vertices from a table scan, hopefully these will be vertices with the maid property key:
for the maid values found above.
Maybe this gives some hints about what is going wrong.
Best wishes, Marc