Feature recognition (FR) for machining planning has most often focused on extracting simple-shaped form features such as holes, slots, rectangular pockets, etc. In Part I of this paper, it was proposed that it is possible to search for more complex shaped features - provided that machining planning for such shapes can be performed automatically and without loss of total machining time. Part II describes the greedy tool heuristic, which can be used as the basis for computationally tractable search strategies to mill complex profiled 2.5D pocket in near-optimal time. A machining planner based on this strategy has been developed. Its successful integration with the FR system previously described justifies the premise that distinguishes the present system from previous ones: maximize the proportion of the delta volume consumed by generalized pockets. It will be shown that machining plans of complex pockets using this method are more efficient than plans based on FR systems using fixed form features. It is believed that this approach for integrated FR and machining planning will lead to more robust process planning systems for practical parts.