Yes, Air Video streams over 3G. Works great on both my iPad on Wi-Fi as well as my iPhone over 3G.
I use Air Video as well, but still use Handbrake to encode everything. This way, I can watch my entire library on my Apple TV at home (without Hacking) and have files I can stream via Air Video without any need for on the fly conversion. It just works.
I agree, it works better than I could have ever imagined over 3G. I too convert mine to save space and as you mentioned, no need for on the fly.