Нашел регулярку для валидации hostname, составленную по спецификации RFC 1123:

^(([a-zA-Z0-9]|[a-zA-Z0-9][a-zA-Z0-9\-]*[a-zA-Z0-9])\.)*([A-Za-z0-9]|[A-Za-z0-9][A-Za-z0-9\-]*[A-Za-z0-9])$

Пытаюсь сделать ограничение {4,40} так:

^((([a-zA-Z0-9]|[a-zA-Z0-9][a-zA-Z0-9\-]*[a-zA-Z0-9])\.)*([A-Za-z0-9]|[A-Za-z0-9][A-Za-z0-9\-]*[A-Za-z0-9])){4,40}$

Она срабатывает на "aaaa", но не срабатывает на "ya.ru", но срабатывает на "yay.ru" или "ya.rur". Также, почему-то не срабатывает ограничение в 40 символов.

Почему так происходит?

чего вы хотели добиться добавив {4,40} ?

Ну обычно я это добавляю, когда мне нужно указать длину строки)) Я взял все выражение в скобки и добавил {4,40}

в регулярках это задает число повторений того что перед этим в скобках, а не ограничение по кол-ву символов.
если надо проверку на кол-во символов, вам проще проверить функцией strlen.