Hi Elijah,
I have the exact same problem as you. However your solution unfortunately did not work for me.
I am using FCP v5.x and QTPro v7.x and Flash Pro 8.0 (not CS3) which also comes bundled with Flash Video Encoder. No matter what I do I can’t get the encoder plugin to appear in any of the supported apps.
I have reinstalled the plugin twice now using your proposed solution without success. My FCP menus look identical to the screen shots you posted.
Any other ideas guys.
cheers
Andrew