I just wanted to add an update to this, because after working with a Microsoft support team I know what the problem is now, in this case anyway. The lists that were broken had outdated urls stored in Outlook. In this group's case, they had at some point changed (at one point or another), the Division site name, the Department site name (a subsite of the Division site), or the name of the list. The paths that I thought were correct were not--they were only slightly off, so I didn't notice the change.
When a list is connected to Outlook, the url of that list is saved in OL in a couple of data files, so that when OL executes the Send/Recieve command, it knows where to go to send or get updated information. The problem is that when the url is changed in SP, those changes to do not get changed in Outlook unless the user re-connects the list. Since they did not re-connect the lists after the url changes were made, the connection had been broken but they were not aware of it (because they spend 96% of their time in the Outlook environment).
You also cannot edit the urls to the SP lists from the Outlook environment, they get hard-coded (or, I lack rights to do so). That means there is effectively no way to push updated data in Outlook out to the SP list if the connection gets broken. The means to do that would be a very useful tool, but I suspect the prevalent attitude would be "make them do all their updates in SharePoint and not in Outlook"--to which I guess I would respond "Then why connect lists in the first place?".
Anyhoo, the local files can be found here (XP):
C:Documents & Settings\User name\Local Settings\Application Data\Microsoft\Outlook
look for: SharePointLists.pst and outlook.sharing.xml.obi
You can view the .obi if you make a copy and open the copy in Notepad. It also handles RSS feeds that go into Outlook.
In the Outlook environment, go to Tools, Account Settings, SharePoint Lists tab to see the urls for the SP lists.
