Ok it was of course my very own fault:
I moved my machine some time ago and got a new IP-Address. An idiot like I am I forgot to update this
in my /etc/hosts file so JNDI lookups went to the old
IP-Address. And because TCP timeouts on linux are very long I couldnt see anything unless today: Someone eventually reused my old IP-Address and as he turned on his machine I finally got an "Connection refused" Exception during JNDI lookup.
Btw. the mentioned shutdown problems also vanished magically once I reflected my new address in the /etc/hosts file.