@Danp - thank you. Yes, I did, but that was not helping in this case.
Found the solution:
Both machines are on a hostserver, which has NOT all networks. So the real reason must be a network problem, therefore a quite missleading error message 🙂
After moving both VMs to the master of this pool (which is connected to the same network where the xoa resides), everything went fine. Same storage, same vhds.