I think an egg-laying animal can be 'gravid' but not 'pregnant' (the latter is reserved for livebearing animals).
I'm not sure exactly about the entire shrimp-sex procedure, and don't know at what stage in the game the eggs are fertilized. I trust that a female shrimp will not release eggs without the presence of a male (chickens and chameleons will lay unfertilized eggs, but I think this is a somewhat uncommon thing).
Here's one thing I know -- you have two male cleaner shrimp, and also two female cleaner shrimp. For a grand total of...two cleaner shrimp. (WHAT?!) Yep. Each cleaner shrimp is a 'simultaneous hermaphrodite', which is a cool way of saying that each is a male and a female at the same time. One shrimp, even though it possesses both male and female reproductive organs, cannot fertilize itself (bummer...), so it needs a partner. But any partner will do (cool...!).
Seems your cleaners had a wild night and each fertilized the other's eggs. Usually they take turns (only one carrying at a time), but both carrying at once is not impossible.
