Il n’y aurait pas de sens à considérer qu’un élément constitutif d’une action ne soit qu’une circonstance de l’action, un cadre à l’action.
— À Paris, je chante. À Paris, je joue à la belotte. Je travaille à Paris. Compléments circonstanciels.
— Je vais à Paris, je rejoins Paris. Complément donnant un sens à la proposition.
On a ici clairement une mise en relation entre une personne et une ville par le biais d’un verbe.
Si on en revient au sens initial de complément objet, Paris l’est très clairement, et comme ce n’est pas un COD, c’est un COI.
Si on veut reconnaître un statut particulier à certains de ces compléments obligatoires qui représentent un lieu, on peut accepter la catégorie intermédiaire complément essentiel de lieu, mais dans une analyse « sujet + prédicat » il sera clairement intégré à ce prédicat, et ne sera jamais complément circonstanciel.

Peut-on dire que dans « l’aiguille pénètre la chair », « la chair » est un objet, mais que dans « l’aiguille pénètre dans la chair », « la chair » cesse d’être un objet, au prétexte d’une construction non directe, alors que son rôle dans la phrase est rigoureusement le même ? Et ce n’est pas un lieu non plus. Ici nous sommes typiquement dans un cas où on a un COI. Quand vous pouvez remplacer ce complément obligatoire par le pronom relatif « où », il peut rester plus parlant de le qualifier de « complément essentiel de lieu ».

Il existe une autre question proche, de la vôtre, et qui a une implication sur l’orthographe.
Dans « j’ai habité dix ans cette ville », mis pour « j’ai habité dix ans dans cette ville », « cette ville » est-il COD ou CEL ? Et donc écrit-on « la ville que j’ai habitée dix ans » ou la ville que j’ai habité dix ans » ? Si la notion d’objet a un sens, alors il faut une réponse à cette dernière question (est-ce un COD ?), et si on trouve une réponse à cette dernière question, nous aurons aussi trouvé la réponse à votre question (est-ce un COI ?).