Postgres ON DELETE Rule Not Working With WHERE Clause
The manual in Rules on INSERT, UPDATE, and DELETE) describes the INSTEAD mechanism for the context of your rule as:


  Qualification given and INSTEAD
  
  the query tree from the rule action with the rule qualification an
  the original query tree's qualification; and the original query
  tree with the negated rule qualification added


Overlooking the part emphasized above would be the cause of the unexpected result.
I believe that in your test case, the mentioned DELETE will be transformed by the rule into commands to the same effect as:

UPDATE categories SET deleted_at = NOW()
    WHERE categories.id = categories.id AND deleted_at IS NULL;

DELETE from categories WHERE NOT old.deleted_at IS NULL;


The DELETE removes the row because the UPDATE before it has just set its deleted_at field to non-null.

Note also the categories.id = categories.id condition which is obviously not needed and comes from the misunderstanding that OLD does not reference a specific row like in a trigger, it's meant to be replaced by the table subject to the rule. 

The main point to understand is that rules don't look themselves at the rows and so they don't generate a kind of IF-THEN-ELSE construct depending on the row contents. The WHERE clauses of the RULES (the qualifications) are not evaluated by the rule system, they are injected into the commands produced by the rule system and will be evaluated by the commands themselves.

See also What are PostgreSQL RULEs good for? and links within for some interesting insights on rules and why they're hard to use.