It is unlikely that remove curse is intended to affect a medusa's curse.
The curse is described in the lore for the medusa:
As deadly as they are ravishing, the serpent-haired medusas suffer an immortal curse brought on by their vanity... A medusa is subject to its own curse. By looking vainly on its reflection, it turns to stone as surely as any living mortal.
Since there is no lore elaborating on the curse or how it might be removed, it is unlikely that the designers intended this particular use of the word "curse" to be read as the kind of in-game condition that, for example, bestow curse can impart. In this case, the "curse" is described as "immortal," so a 3rd-level spell is probably too weak to remove it.
An elaborate justification for the preceding claim.
There are other creatures described in the Monster Manual as suffering from a curse for which the provided lore does describe how to remove the curse and what the results would be. The examples relevant to this argument include lycanthropes and mummies.
Let's first look at the mummy:
Raised by dark funerary rituals, a mummy shambles from the shrouded stillness of a time-lost temple or tomb. Having been awoken from its rest, it punishes transgressors with the power of its unholy curse.
Ending a Mummy's Curse. Rare magic can undo or dispel the ritual that gave rise to a mummy, allowing it to truly die. More commonly, a mummy can be sent back to its endless rest by undoing the transgression that caused it to rise.
So, the mummy suffers from a curse, but it requires "rare magic" or narrative gimmicks to remove, and the lore describes exactly what happens when the curse is removed (the mummy dies). Whereas the lycanthrope's lore does describe rules for using remove curse to lift its curse, the mummy's lore uses the phrase "rare magic" instead of naming any spells. The implication is that "rare magic" includes spells far rarer than a 3rd-level remove curse that any old 5th-level caster can learn, spells so rare they can't be named and are unlikely to be widely known.
If the designers intended for the "immortal curse" of the medusa to be removable, we would expect a similar level of detail as provided in the lore for the lycanthrope and mummy. In the absence of that detail and with remove curse implied to be too weak to remove a CR 3 mummy's explicitly removable curse, it is unlikely that remove curse is strong enough to remove a CR 6 medusa's "immortal curse" which is not even indicated to be removable.
Therefore I assert that the designers did not intend for the curse upon a medusa (or many other "cursed" creatures in the Monster Manual) to be lifted by remove curse.
The usual caveat for DM fiat.
Of course a DM could choose to allow it in the interests of an entertaining narrative, but for the given reasons I think that violates the design intent.