Sorry if you already did this, but have you checked if the system messages part of your mailbox is full? Although you can receive lots of mail from other players, you're limited to only 20 system message (from Square Enix) so if you are at that limit you'll need to delete something before new things can arrive (they will still arrive, but they need space to do so).