One of the bigger problems I encountered was that the original software wasn't perfect, so the first step was to replicate it, bugs and all and only then to fix the bugs. So the FAA never entered into it but the Dutch equivalent did. Also, I think there is a big difference in stuff in use in GA versus that which is used for commercial aviation. We're talking early 90's or so, so the details are a bit hazy by now.
Interesting job though, that's for sure, lots of good lessons from that one. I'd never been sent back four or five times by an auditor because my work wasn't up to their standards and every time they sent me back they had a valid point, it wasn't bs just to check a box somewhere, they had valid concerns and I had to rework some of it quite extensively. At the level of "I don't care if the answer is correct, I need to understand why it is correct".
I would suspect that certification would break down at some point; does a plain old calculator need to be certified? Certainly not, but I'd imagine the FAA or whoever if asked would prefer pilots use calculators than do everything by hand.
I'm curious about EFBs as well - I run W&B for my little bugsmasher in Foreflight. Has that gone through certification? Certainly someone from the FAA wouldn't have to review every release for that if so...
So when does certification come into play versus it just being another tool that pilots are responsible for validating?