Bitcoin.de does not handle fiat.  It is more similar to Localbitcoins than MtGox.

Bitstamp can not have been entirely honest with their bank, since some of what they are doing is illegal.  Bitstamp has put all their eggs in one basket.  Any problems with that bank, and their customers will be quite deep in it..

MtGox are negotiating with the same bank that Bitstamp is using.  It is very important to MtGox that their bank understand what they are doing, and to ensure that MtGox and their bank operate safely within all regulations (contrary to Bitstamp).  According to MagicalTux this takes longer than expected.

You could have mentioned Bitcoin-Central as an example.  Bitcoin-Central was headed in the right direction by basically getting lisenced to operate as a bank themselves.  Customers were about to get their own IBAN at Bitcoin-Central when they had to close due to a security breach at their hosting provider.  I hope they'll open again soon.