From what I understand, even when data is overwritten on disk there is a possibility of it being recovered. From what I also understand, replacing/deleting a LUKS key is fast/trivial and does not lead to all the data being rewritten. This suggests to me that there is an important "secondary key" somewhere in the header, which further suggests that if a key has been compromised and replaced, but an attacker can recover a PREVIOUS state of the LUKS header that used that key, they could still access the data. Am I wrong or is this a security concern?
The short answer: This is a security concern if you fail to maintain physical control over your media and/or choose poor pass-phrases.
If an attacker gains access to the hard drive at time A, duplicates it, and compromises the key as it was at time A, then all of the data that was present at time A is compromised (but you knew that part).
To the best of my knowledge there is a 'master key' that each passphrase will give you access to. Further, there is no way I could find to easily change the master key without creating a whole new partition for the new master key (it would be hard to do even if it were possible).
What this means is that unless you wipe the hard drive and start over between times A and B then the attacker who compromised the key as it was at time A, and who also gains access to the same drive at time B, has access to the data as it is at time B.
User education and proper response to security threats. If your user loses control of encrypted media and then regains control of it later, you need them to tell you about it, and you need to wipe the machine and re-encrypt it using a different pass-phrase.
Also, count the information that was on the laptop (at time A) as lost or potentially lost if there is any chance that a sophisticated attacker gained access to it and the pass-phrase isn't quite strong.
As a very short summary of the parts of the LUKS header that are relevant here (not necessarily intended to be 100% technically accurate):
When you create a LUKS container, a random master key is generated. This is the encryption key that is used to actually encrypt the data on the drive. You are also prompted for a passphrase, which is used to derive an encryption key for the first key slot. The key slot encryption key in turn is used to secure the data in the key slot, including the master key.
Until semi-recently, LUKS had no convenient way to change the master key; it was essentially "burned into" the container at the time of creation. This was a problem for example if container creation happened in an entropy-starved situation, such as early during initial system installation. Nowadays (since cryptsetup 1.5), there is cryptsetup-reencrypt which is provided by default in modern distributions, which among other things allow you to change the container master key by re-encrypting all the data in the container.
A LUKS header backup contains all the data that the LUKS header contains. In other words, the master key, protected by (possibly a set of different) passphrase(s). It is equally possible for an attacker to attack the LUKS container through a header backup or a copy of a detached header, as through direct access to the container.
Hence, if an attacker has access to the LUKS header for a container, they can attack the key slots at their leisure. Once they are able to pry open one of the key slots, they have the key that would be used when the header was dumped to decrypt the data in the container. If the header that the attacker has access to was protected with a weak passphrase or with weak PBKDF settings (particularly the iteration count), this may be a problem.
Again hence, unless you reencrypt the container using a different key (you can stay with the same cipher and cipher settings), such an attacker can use the master key they now know about to access the data in the container at some later time.
To mitigate against this threat, it is not sufficient to change the passphrase; you have to reencrypt the container.
Of course, if the attacker was able to duplicate not just the LUKS header but also the contents of the container itself, and the attacker manages to pry one key slot open, then the data is instantly compromised.