Shortly after the previous post we were able to convince SBC to remove the block on mail coming from our network.  The issue remains tricky because they do not inform us when changes occur and tend to make decisions without investigating first (at least in our case).  So for now, the SBC problem is behind us.