When a category (has been deleted or has never existed) and it has no members (ie. there are no articles in the category) then an HTTP 404 code should be returned.
Consider http://webcache.googleusercontent.com/search?q=cache:tA61J-kDRkMJ:en.wikipedia.org/wiki/Category:Elysiidae which is Google's cache of en:Category:Elysiidae. Google is continuing to report it even though the category was deleted more than two years ago. It is reported because a status code of 200 OK is returned. Presumably the idea of that was to allow for categories with members but without a category page.
Solution 1 - cheap and, in my view, completely satisfactory. Forget the "no members" criterion. Return a 404 Not Found code for every category where no page exists. Most browsers completely ignore the difference between a 200 and a 404 code - an human viewing a category with members but with no page will see the information and never know that a 404 was returned. Search engines seeing such a page will honour the 404 and not index - is that any great loss?
Solution 2 - rigorous. For a category where no page exists, check first if it has members and send 200 or 404 as appropriate.