Hey, it's good to see that someone has the MT9D111 working with an Arduino. Are you using a FIFO to buffer the image data?
I'm using one of these things as well, although I gave up trying to get things working with the Arduino and went with the mbed platform.
Here's an 800x600 JPEG I was able to get off the device (JPEG is a bit tricky to get working, but seems pretty stable once things are set up right).http://imgur.com/azLSMjc
I do have a question, though. Does your device's EXTCLK run at 1/5 the speed in capture mode, as opposed to preview mode? That's what mine is doing, and I can't find any mention of that behavior in the datasheet or developer guide.
Edit: The image didn't show inline so I linked it