I couldn't find any good references to this online, and I am not an English teacher.
Consider this a native English speaker's perspective.
Does this usage of again sound natural?
Yeah, in a natural conversation or when reading casually, I wouldn't notice this as strange. Even if I were to scrutinize a piece of writing containing this sentence I probably wouldn't notice a logical flaw. If I notice anything at all it's only because you have already pointed it out.
Is this usage correct?
A harder question to answer. My initial gut feeling is to say, technically, no it's wrong. But I think the meaning you are going for here, and possibly why it feels correct/natural, is that you are using "again" to emphasize that the two men were previously outside the room, and now they are once again returning to their previous state of being outside the room.
If I were to rephrase your sentence to bring across this specific meaning:
Two men step into the room, look around, find nothing, and once again return to the hall.
In conclusion - if you want to use this phrase, it is unlikely a common reader will notice, be confused, or care. However if you are still worried about it, you can rephrase with or without "again".