Here's a 2013 version of their password hashing file[1] which should confirm that they were using the (very crappy) method back then.
OSCommerce, which Magenta was attempting to replace, had password hashing as far back as 2006.
Maybe you're thinking of a different service?
1. https://github.com/nexcess/magento/blob/master/app/code/core...
That sounds to me more like they were dealing with the Meganto support portal rather than the Magento ecommerce software itself - a quick peek right now suggests that's Zen Desk. I don't know if ZenDesk admins have access to cleartext user passwords, or if Magento's ZenDesk agents regularly ask people for passwords and have a means of verifying them - but it's not a good look either way.
https://raw.githubusercontent.com/OpenMage/magento-mirror/ma...
I don't remember who I was talking to exactly but they said something like "and you're logging in with the username <whatever> and the password (fading awkwardly) MagentoSucks..."?
And we both kind of laughed nervously...