Should all validation rules be tested within a Cucumber feature?

This is a good question, and the answer is: It depends.

You can think of Cucumber as a way of communicating between the product owner, developers and testers.

If you feel that having the validations in Cucumber adds to the shared understanding of what the product does, then keep them there.

One approach is to combine the validations into a scenario outline:

Scenario Outline: User tries to register but skips a mandatory field
  Given I am registering
  And I leave the "<field>" blank 
  When I click "Submit"
  Then I should see "<message>"
  And I should not be registered
    | field         | message                         |
    | Forename      | Please enter your forename      |
    | Surname       | Please enter your surname       |
    | Date of Birth | Please enter your date of birth |