What about DivX/XviD?
VCDs had broad hardware support, and were more mainstream.
I used to travel around Southeast Asia a bit, and whenever I was in Hong Kong, I'd load up on VCD movies at mainstream stores like HMV.
I still have VCD copies of The Incredibles and On Her Majesty's Secret Service I bought at HMV.