[Tayfun Tuna]

This may sound odd, but I sometimes need to record low resolution (so, low size) videos, convenient enough to send over data connection when data quota is an issue.

Is this possible, if so, with which application?

I own a Lumia 720 with the black update.

[Nokia Boy]

I think the only solution is to convert it using a PC Software such as Freemake Video Converter (Which is Freeware)

[xandros9]

Is there a 3rd party camcorder with that option? I would think its possible.

But from the default camera's nope. Your best option otherwise would be to downgrade/compress them on a computer using Windows Movie Maker or other editing tool