JohnB, yes the legacyExchangeDN will still point to the non-existent admin group. But no, nothing should break. Ever since Exchange 2000, you've been able to move mailboxes to a new admin group and delete the old one. That was a feature of Native Mode move mailbox, and it doesn't change the legacyExchangeDN. Because of that, it's actually quite common and normal to have legacyExchangeDNs on mailboxes that point to an admin group which no longer exists.
B.M, that's a different problem with a few causes. One cause is simply not having permissions. You must have at least Contributor rights to the public folder. Another cause is an improperly formatted P2 header (the "To:" line) when the email is coming from an external sender. For instance, if the To: line contains just a display name and no actual email address, this happens. Yet another cause is hierarchy replication failing so that we don't see the folder on certain stores. If you can't track down the problem, get a case open so we can find out what's going on.
JH, I'm trying to find your open case so I can review it, but I'm not having much luck. If you click on my name to go to my TechNet blog and then click on the Email link there to contact me, I'll look into it.