Το μαγαζί του είναι πάντα γεμάτο πελάτες.

English Translation

His store is always crowded with customers.

Would I correctly expect a genitive here? I suppose γεμάτο … is such a common phrase that it lost the declension?

The genitive here would be in a more formal register. The accusative seems to be more common.