Although previous studies suggest relatively consistent patterns in responsibility attribution for AI-mediated service failures, this knowledge is largely based on quantitative research designs. Drawing on semi-structured interviews, this paper examines how customers construct and attribute responsibility during AI-mediated service recovery and how these interpretations shape their relationship with the firm. Findings suggest that responsibility for the service failure and responsibility for the service recovery are attributed in parallel and independently of each other. This creates a state in which customers can hold the company fully responsible for the error, while simultaneously being able to attribute responsibility for the process through human enactment. AI, influenced by perceived agency, served as a buffering layer amplifying ambiguity during the service recovery. Failure severity shapes customers evaluations across the entire recovery process, extending its role beyond existing conceptualizations. Sensemaking proved to be an intricate, ongoing process which, through cues, contributed to revisions of their interpretation and uncertainty during both the service recovery and beyond the resolution point. These dynamics led to relational recalibration towards the firm, where evolving perceptions of the firm did not automatically lead to changed purchase behavior, suggesting that customer retention should not be interpreted as evidence for a restored relationship.