HMAC-SHA-512 with a 256-bit key
In what way does using a 256-bit key rather than a 512-bit key with HMAC-SHA-512 decrease its security strength?


It doesn't, in any real sense.  With a 256 bit key, it can be broken by searching through a key space of size $2^{256}$; a simple computation on the energy required to do such a search shows that it is ludicrous (and is the source of the 'Dyson Sphere' comment made by CodesInChaos).

If we assume that the attacker had a working reliable Quantum Computer, he could, in theory, attack the system by performing $O(2^{128})$ HMAC-SHA512 evaluations, which is still not very practical, but not nearly as ludicrous.  However, to achieve such a 'low' number of computations, he would have to perform those computations serially (which would extend the total time taken to do the search to something longer than the current age of the universe).  Yes, he could speed things up by using multiple parallel Quantum Computers, but it turns out that drastically increases the already huge number of evaluations required.

There is no known way to attack the system with any less effort; hence the system is quite secure against any even remotely plausible attacker.