I have laptop with P2/366MHz/192MB RAM and:
- don't have any problem with VCD playback
- to watch DIVX smoothly I have to: 1) close all non-essential applications
2) resize screen to 800x600
3) change color depth to 16-bit
So, I'd say that p2/366 is not much under the speed limit for playback of divx files, probably P3/500+ will do without trouble.
As mentioned by many, for just VCD everything better than 486 should work just fine