We have recently been having a lot of issues with tags and categories misbehaving in wordpress and I finally figured out the solution. Since it was anything but obvious I thought I share my findings.
First the symptoms:
It all started with sporadic and unreproducible disappearance of categories in the wordpress admin interface. For some reason it did not cause any obvious problems on the mosabuam site. The VIJUG site however had the categories disappear in the menu. This problem was not visible since we are not using categories on the main site, but e.g. the tagcloud links stopped working. In the end even the main page of recent posts stopped working and just showed an error message that there are no post for these criteria (not mentioning which these are..).
Looking at the database schema I found a bunch of inconsistencies that mostly acted as detractors from the the real problem. Fixing some of them up by deleting orphan records, giving descriptions to all categories and tags and such sometimes seemed to make things better, but now I have a feeling it might all have been sheer coincidence. Searching around on google and various other places did turn up similar problems, but all measures suggested did not help.
And then the source of the problem and the solution:
However fuzzing around with mysql via phpmyadmin I found that we got more and more error messages like
SQL query: Edit
SHOW FULL FIELDS FROM `wp_terms` ;
MySQL said: Documentation
#1 - Can't create/write to file '/tmp/#sql_559_0.MYI' (Errcode: 28)
whenever I selected any table in any database in the structure view in phpmyadmin. It also appeared whenever I tried to edit a row in the browse section of phpmyadmin. After searching for a problem like that related to wordpress and mysql on the web I found this link and concluded that even though this talks about a much older version of wordpress (we are at the latest all the time.. currently 2.8.4) the problem might still be the same. And lo and behold it was. Getting my hosting provider to fix the problem with the access rights in /tmp resolved the issue. Fingers crossed it stays like that and a big #fail to WordPress for failing silently and MySQL for buggering up the first place.