Is this DIY remote lock protocol secure?
Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC.

I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. Unless you have a good reason to use MD5, I would also prefer to use a stronger hash, though HMAC-MD5 is still secure (that is about encrypted data, but applies generally).

However, I do not think the weaknesses actually apply here, since the attacker does not have freedom to choose the values they need to calculate the keyed hash for. So even as is it should be secure. Despite that I would recommend switching to HMAC. Even better would be to use an existing mutual authentication protocol meant for this purpose, like the one descrived in Chapter 10 of HAC (see 10.2.3).



The below applies to the protocol as described in the original version of the question.


  
  Key generates completely unique value that never repeats (some kind of a counter), let's call it "NONCE1".
  Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1)
  Lock checks if H1 = MD5(NONCE1 + KEY1)
  


This part does not prove anything to anyone, so it is useless. An attacker who impersonates the key can reuse any previous nonce+MD5-pair because the lock does not know if the nonce is unique. An attacker who impersonates the lock can simply ignore the data received.


  
  Lock generates completely unique value that never repeats, let's call it "NONCE2".
  Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2)
  


Why not simply send NONCE2 to use as H2? The hash does not seem to help in any way, because the nonce is not used for anything else.


  
  Key does H3 = MD5(H2 + KEY3) and sends it back to the lock
  Lock checks if H3 = MD5(H2 + KEY3) and acts on that
  


This is the only part of the protocol that has a clear purpose: the lock is verifying an ad-hoc MAC to authenticate the key.