I havent used it, so Im not sure if it has airplay support, but have you tried the "VLC" app?
O Player HD plays just about everything, its not free though
Native airplay?... even on mkv/avi's?... or you mean airplay with mirror option on?
it plays full screen on my HD TV, so not just standard mirroring.
Is there an app which can airplay all formats to ATV not only mp4/mov?
For example AVplayer HD airplays only iOS formats.