@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.