Made lots of tests with different codecs and settings.
MJPEG has problems playing in reverse. Maybe this can be fixed as ksp wrote with keyframes every frame but I don’t have that option in AE CS5, because “Advances Settings/Keyframes” checkbox is grayed out.
Then with MPEG Streamclip exported from an AVI file with no compression to an AVI ‘Apple Cinepak’ compression with 100% quality and it works very nice, going forward and backward at different speeds.
My file is 1920 x 1080 px @ 30 fps, 921 MB and the CPU is i5, 4 GB RAM, GeForce GTX 460, Windows 7.
Didn’t get to try Plan B (image sequences).