"FIPS compliance" is about more than the algorithm. It is about implementations. Being awarded the "compliant" badge is a long, complex and very expensive process; its conceptual meaning is that there are some strong reasons to believe that the implementation is correct and secure and fulfils a number of security properties. Since we don't really know how to prove that software is correct in all generality, most of FIPS compliance is done through audits and analysis of development process. This is rather thorough; this includes, for instance, making sure that during development, source code versioning was used, with proper attribution of each line of code to a properly identified developer, for whom some background checks were performed.
In practice, getting compliance implies producing a lot of paperwork (many thousands of pages) and even more auditing, for a cost that easily goes to $50000 or more, and takes up months. Costs grow up quickly with the scope. Apparently, in 2007 (from your link), Microsoft went through the whole ordeal for HMAC/SHA-1 but not for HMAC/SHA-256 or HMAC/SHA-512, which is why the former is "FIPS validated" but not the latter.
This may be related to the fact that back in that time, .NET could use the SHA-1 implementation from the Win32 layer (CryptoAPI), in native code, while SHA-256 and SHA-512 were "managed" code; doing FIPS compliance for HMAC/SHA-256 with the managed implementation (
SHA256Managed) would have thrown the CLR runtime, including the JIT compiler, within the scope of the auditing, and price would have probably skyrocketed. A native implementation of SHA-256 was added in .NET 3.5 (
SHA256Cng) but it was released only at the end of 2007, too late for the compliance shown in the list you link to.