I've tried with go-online too (sorry I forgot to list it in my post), it still doesn't work.

Some more investigation: When I do 'hamachi list' on each device I see:
* [my network name]
x 5.x.y.z

on each device, with each other's 5.x.y.z address. Reading the docu 'x' means '.. the peer is unreachable, ie the mediation server failed to establish p2p tunnel between you and the peer.'.
So I guess that's where the problem is. I wonder what could cause this. Anyone found a FAQ for hamachi yet?