Q:

HMAC-SHA-512 with a 256-bit key

I am implementing hmac-sha-512 in an integrated system. However, one subsystem is only supports the use of 256-bit keys.
I read in https://tools.ietf.org/html/rfc4868 that:

However, note that [HMAC] strongly discourages a key length less
  than the output length.  Nonetheless, we describe handling of
  shorter lengths here in recognition of shorter lengths typically
  chosen for IKE or IKEv2 pre-shared keys.

And also:

These key length restrictions are based in part on the
  recommendations in [HMAC] (key lengths less than the output length
  decrease security strength, and keys longer than the output length do
  not significantly increase security strength), and in part because
  allowing variable length keys for IPsec authenticator functions would
  create interoperability issues.

In what way does using a 256-bit key rather than a 512-bit key with HMAC-SHA-512 decrease its security strength? Is it not advisable to proceed with a 256-bit key?

A:

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.

