I've finished it once, but I haven't been able to do all missions. I understand that to get to some you would e.g. need to fail on certain missions (good example: having the Metal Slug destroyed in some levels requires you to escape Prison Camp and go onto a different mission, whereas being shot out of the Slug flier parachutes you out into a different mission).
Great game. The sequel was fun too. Seems like I couldn't finish half of my NGPC games 100% with all secrets because of either missing another NGPC with a link cable or there not being any FAQs. Sonic had all those secret pieces that were impossible to find.