Step 1. Install ffmpeg.
I believe I downloaded it from here
There was issue with the installation. After installing it (in c:\windows I believe), I noticed that none of the presets worked. This is natively a linux app, and after a bit of poking around I saw that it was looking for the presets in /usr/local/share/ffmpeg.
To fix this, I created that folder in the root of the disk I was using for the transcoding (X in my case), and put the preset files in there. After that, it worked like a charm.
Step 2. The handy dandy ffmpeg command with some batch wizardry:
The windows Imagemagick packages has a ffmpeg binary bundled in. As a bonus, it appears to work better in my limited testing. Download it here
To rotate 90 degrees.