Increasing operational complexity within port and logistics industries has intensified the importance of operational responsiveness, service recovery, and Costumer retention. Nevertheless, the mechanisms through which service excellence and complaint resolution influence competitive advantage and Costumer loyalty within operational service environments remain insufficiently explored. This study examines the relationships among service excellence, complaint resolution, competitive advantage, and Costumer loyalty in the operational context of PT Pelindo Regional 2. Drawing upon Relationship Marketing Theory and the Resource-Based View, the study positions complaint responsiveness and operational recovery capability as strategic determinants of organizational competitiveness and Costumer retention. Using survey data collected from 316 companies utilizing PT Pelindo Regional 2 services and analyzed using Partial Least Squares Structural Equation Modeling (PLS-SEM), the findings reveal that complaint resolution significantly strengthens both competitive advantage and Costumer loyalty. Service excellence also positively influences Costumer loyalty; however, it unexpectedly exerts a negative effect on competitive advantage. Furthermore, competitive advantage does not significantly influence Costumer loyalty and fails to mediate the relationships among the examined variables. These findings reveal the existence of a service-performance paradox within highly operational and infrastructure-based industries, where Costumers prioritize operational responsiveness and recovery capability over symbolic organizational superiority. The study contributes to service management literature by emphasizing complaint responsiveness as a more strategically relevant capability in sustaining Costumer loyalty and organizational competitiveness within port service industries.