I had an issue similar to what is described here. I turned out that I had to restructure my code slightly before I could adjust the video size.
The important thing is that setVideoSize() is called before setVideoEncoder(). I can't find this in the documentation, however it solved my problems with setting a specific video resolution.
Also keep in mind that setOutputFormat() should be called before setVideoSize().
As as side note the same is true for setVideoFrameRate(). If it is not called before setVideoEncoder() it will not have any affect.
This was tested with Android 2.3.3
Here is a code example:
recorder.setAudioSource(MediaRecorder.AudioSource.DEFAULT);
recorder.setVideoSource(MediaRecorder.VideoSource.DEFAULT);
recorder.setOutputFormat(MediaRecorder.OutputFormat.MPEG_4);
recorder.setVideoSize(640,480);
recorder.setVideoFrameRate(30);
recorder.setVideoEncoder(MediaRecorder.VideoEncoder.DEFAULT);
recorder.setAudioEncoder(MediaRecorder.AudioEncoder.DEFAULT);