The value passed server-side for the Search Box (sSearch) is not consistent. Initially, with no text in the Search field, sSearch is passed to the server as an empty string (""). However, if the box has been populated, then cleared, sSearch is passed as the string "null". Not sure if this is a bug or feature! ;-)
I've also just tried it on my client-side processing demos and it appears to work okay there. Can you use the debugger ( http://debug.datatables.net ) on your table when this problem occurs please?
Sorry I haven't had a chance to look at this yet - I've added this to my pre-1.9.1 list to make sure I do look at it before 1.9.1 is released (which will be next week now).