You're right, it is a surprise that you can connect from anywhere with a hosts.deny file that is set to deny everything except traffic from the localhost.
Perhaps there are some more exemptions in /etc/hosts.allow that for some reason allows NODE2 to connect.
If I was you, I'd start by looking at these files.
First, comment-out all the lines in /etc/hosts.allow and /etc/hosts.deny.
Now re-try your SSH from NODE1 -- if it works, you know these files are the problem.
I wouldn't leave everything commented-out though, it's a bit of a security hole. If it does fix it, you should probably read up on these files and find a way of allowing the traffic.
Probably something like: