I was astonished to discover an Android video player that supports native Divx flawlessly.
It's called RockPlayer, and it has played every single Divx file I've loaded onto my SD card, as well as some M4V and MP4 files. Others have even been able to play HD MKVs, but the ones I tried played, but just barely.
I'm running it on my Droid Incredible, but many Droid users have reported excellent results.
The only bit of bad news is that the beta expires on July 15th. Whether they'll provide a new release with extended expiration is unknown at this point, but they are actively developing the app.
Here's the link for the APK: Download RockPlayer for Android
There's also a support forum located here.