Well, not really Xen related, but I noticed that our blades became unreachable once the bridging scripts had run.
After reading a lot of bug reports about bugs in the default Xen networking scripts, a posting on the Xen mailinglist pointed me in the direction of the network driver.
Apparently, some versions of the Broadcom NetXtreme II network driver are somewhat buggy which reflects in broken bridges. In particular, the version included with the binary distribution tarball of Xen 3.1 is affected.
Luckily for us, the bnx2 driver included in the 2.6.18-6-xen-686 kernel available in Debian etch is OK and after a reboot, I had my fully working bridge.
I hope this post reaches other people with the same problems, because it cost me a lot of time to fix.
Update: This problem also occured randomly on some of our other servers, all running the same Xen 3.1 bnx2 driver. After an update of the kernel, these problems disappeared.