First, there is no such thing as perfectly secure information system. The best we could do is mitigate identified risks. The best any standard could do is specify how to mitigate specific risks.
In case of NIST CAVP (part of FIPS testing most people are familiar with), the risk they are mitigating is that cryptographic algorithm you are using is flawed in some way. This certification program is hugely successful, there are robust standards and specs, and hardly anyone these days end up with bad algorithms because free certified reference implementations and free testing vectors were made available.
Second, different aspects of FIPS program focus on different risks. For example, at higher certification levels (e.g. CMVP FIPS 140-2 Level 3 or 4) the program provides very robust and comprehensive assurance that both algorithm and methods of use of these algorithms within cryptographic module is secure. I am too lazy to dig through the specs, but I am positive that at level 3 it explicitly examines key storage. The flaw with FIPS is actually opposite of what you state - the level of scrutiny ramps up so rapidly that it is impossible to satisfy it only with a software implementation at above level 2. As a result, overwhelming majority of certifications are against lowest tiers that are limited in scope.
Now, people look at CAVP certification (algorithm testing for software product) and make ignorant statement that the ENTIRE FIPS PROGRAM is ineffective. Even when it is very evident that it accomplishes exactly what it promised to do. To leave you with an example - PCI (payment transactions) requirements cap at FIPS 140-2 level 3. This is stuff that touches MONEY! FIPS 140-2 level 4 is spook-level robust, they even have a requirement to trip zeroization if you attempt to freeze or x-ray the chip.