I found the problem.
It turns out that if you remove an individual cookie from Firefox, Firefox decides that you must hate the site that gave you that cookie, and automatically, without telling you, blacklists that site from receiving any future cookies. And the only way to even find the UI that contains the list of blacklisted sites is to change the option on the Privacy settings page to "Use custom settings for history" (which then shows an Exceptions button).
It turns out that if you remove an individual cookie from Firefox, Firefox decides that you must hate the site that gave you that cookie, and automatically, without telling you, blacklists that site from receiving any future cookies. And the only way to even find the UI that contains the list of blacklisted sites is to change the option on the Privacy settings page to "Use custom settings for history" (which then shows an Exceptions button).