Voilà deux termes présentés dans tous les dictionnaires usuels comme adjectifs (et participes passés).

Si, partant, l'accord avec la ou les personnes censées s'exprimer ne souffre aucune contestation dans les formules de politesse usuelles (Nous sommes désolés de vous avoir fait attendre. Elle est enchantée de faire votre connaissance), la question peut se poser dans les tours elliptiques propres au registre plus familier. Ainsi une femme doit-elle s'excuser d'un « Désolée ! Je t'ai menti » ou d'un « Désolé ! Je t'ai menti » ?

Vous me direz, à bon droit, que la différence ne s'entend pas à l'oral, mais faisons l'effort de nous pencher sur la question dans l'éventualité d'une lettre... de rupture, par exemple. Bon, je vois bien que cela ne vous enchante guère, que vous trouvez l'exercice inutile. Vous m'en voyez sincèrement... désolé ! Sans doute considérez-vous que, s'agissant d'un tour elliptique, il suffit de reconstituer la phrase dans sa totalité pour se déterminer : Désolée ! Je t'ai menti, sous-entendu Je suis désolée ! Je t'ai menti. L'accord de l'attribut avec son sujet s'impose à l'évidence.

Et pourtant... Certaines sources ^(*) avancent que lesdits adjectifs, placés en tête de phrase, auraient valeur... d'interjection ! Entendez, seraient donc invariables : Désolé, nous ne faisons plus cet article. Bigre, quelle désolation !

La confusion provient, d'une part, de ce que certains écrits hésitent entre les personnes du singulier et du pluriel quand l'adjectif est éloigné de son sujet  : « Désolé (pour : je suis désolé), vous avez trop peu d'expérience. Nous ne pouvons donner suite à votre candidature », là où, en toute logique, il eût fallu écrire : « Désolés (pour : nous sommes désolés), vous avez trop peu d'expérience... ». D'où cette impression trompeuse d'invariabilité. On pense, d'autre part, à ces messages automatiques et anonymes qui fleurissent sur nos ordinateurs et sur nos téléphones : « Désolé, vous n'avez pas accès à ce service ».  Sans doute peut-on considérer, dans ces cas particuliers où l'on ne saurait dire qui s'exprime réellement, qu'il s'agit là d'un accord avec un « neutre singulier », sans pour autant considérer désolé et enchanté comme des interjections (invariables).

(*) Wiktionnaire, Reverso et autres sites dont la fiabilité est parfois sujette à caution.

Remarque 1 : En présence d'un nous de majesté ou de modestie, d'un vous de politesse, l'accord se fera correctement au singulier.

Remarque 2 : L'adjectif désolé a également le sens de « inhabité, désert » ; enchanté, celui de « qui est sous l'effet d'un enchantement, merveilleux ».