Update: Here, probably the last update on Video conversion.
Okay, as I said before, used Total Video Converter for some files that didn't have sync problems.
As for some 30+ others, I used a free soft that looks very VERY amateurish-like. It's called AlltoAvi, and you can find it on http://sourceforge.net/projects/alltoavi/
Seems it was developed by some anime fan, which is perfect for me since I'm converting anime files. Interface maybe kinda fugly and confusing, but after you get it working, batch works nicely. Also, it's just a GUI for a command line tool that converts video.
Doesn't support as much codecs as Total Video Converter, but the same videos that ended up with sync problems with TVC, with AlltoAvi worked just fine.
And that's it. When I have the time (not now, I'm getting on a bus just tomorrow) I'll compile all the information I got in the past couple days and compile it to a tutorial.
Summary: Total Video Converter has the best GUI, collection of codecs, and options. It is commercial though, and lots of files I tried to reencode (Mostly .avi files) resulted in sync problems.
AlltoAVI looks amateur, fugly, confusing and buggy. But got the job done. It's actually a GUI interface for a command line converter.