Is it possible that the key is incorrect but still decoded to a valid message? I realise it's possible when you're using keys that are the same length as the message, but I don't know exactly how the Enigma machine works and if this was something that they would do or not.