Try renaming the "views.dat" file on the client pc to "views.old" to make a backup of it. You can find the file at "C:\Program Files\Hewlett-Packard\OpenView\service desk 4.5\client\data\" and at "C:\Documents and Settings\[name of user]\Application Data\Hewlett-Packard\OpenView\Service Desk". Once you've re-named those, re-login to Service Desk. The views.dat should be re-created, and you might have better luck with that search. If not, you can rename the views.old back to views.dat to restore it.
The other .dat files in those directories might also be the source of the problem. You can try backing them up in the same way if getting rid of the views.dat doesn't fix the problem.