Justin -- I will try to give you a couple of ideas on how to handle things. But, my specific suggestion would be to use the Activity Percentage System from RMC.
I gave the AP system a try once myself, but had a number of issues, like you, and thus gave it up, though I did like the "Min AP Cost" idea, it was always more complicated than it seemed worth it. I even created a second-by-second system that used time reductions (this was for RMFRP at the time), If you are interested, I have it in my downloads section on my personal website.
1) Movement -- If you, as the GM knows that the monster is going to be moving as well, you may need to tell the players this, and give a guesstimated point of meeting, and have them figure out their AP from there.
2) I think that perhaps you are doing the movement math wrong. Using the general formula found in the bottom right corner of page 17, I get that it takes 8 AP (not 350) for a normal character to move 50' at a Dash Pace. Let's work the forumula... (we will use BMR of 50' for this example)
AP Cost = 40 x [# of feet Moved / (Movement Rate x Pace Multiplier)]
AP Cost = 40 x [50' / (50' x Dash (i.e. x5))]
AP Cost = 40 x [50' / (250)]
AP Cost = 40 x [0.2]
AP Cost = 8
OR
Using the small table, just above the general formula, a character with a BMR of 50' who wants to move 50' will use 40 AP to move that distance at a walk. If he is Dashing, that gives him an adjusted BMR of 250' per round, so moving 50' is closest to 1/4 (from the table) Movement Rate, thus costing 10 AP.
3) I think that perhaps your issues with determing movement AP is causing a large part of the problems.
Crits that grant Initiative -- My suggestion here is to just let the character who has initiative go first, perhaps by giving an AP penalty to the other character (i.e. Fighters A & B -- B does a crit that says he has init over Fighter A -- thus, just make Fighter A's next action cost a number of additional AP equal to half of the AP for Fighter's B's next action).