Some follow-up on this. Elsewhere, Origen uses a similar phrase in Contra Celsum, in a context where he quotes all of Rom 1:21-28--interestingly, except for Rom 1:26b. He has a larger discussion of these verses, and the discussion is interspersed with the quotes of the verses. Where we might expect to find Rom 1:26b (the women who exchange natural relations for unnatural), instead we find:
"εἶναι θεοῖς παρθένοι"
So if I take this finding back to the commentary fragment, I think it supports the interpretation that παρθένοι τῶν εἰδώλων from the Romans Commentary fragment are a reference to the women in the goddess cults, such as the Vestal Virgins.