The VX8500 can handle 3GPP (3gp and 3g2) and mp4 containers. The video format needs to be one of the standard H.263 MPEG-4 codecs and the audio should be AAC format.
There are two methods I have devised for converting videos to 3g2/mp4 format that the VX8500 can play. The simple method gives good results with most kinds of videos. The preferred method involves a couple more tools, but will result in the best possible quality of video for the Chocolate.