Flexible Plan Verification: Feasibility Results