La rue que j’ai habitée n’existe plus : ici « que », pronom qui reprend le nom « rue ». Il est COD et placé avant le verbe conjugué avec l’auxiliaire avoir : l’accord se fait.
La rue où j’ai habité n’existe plus.

Vous avez l’impression de dire la même chose, et pourtant non.
Ici, vous avez repris le nom « rue » par « où » qui est un pronom complément circonstanciel de lieu. Du coup, le verbe « habiter » n’a pas de COD : l’accord n’a pas lieu d’être.