Так как же все-таки правильно прикреплять домены и поддомены к хостингу, какой самый правильный способ?
Оба варианта правильные.
По поводу непоняток во втором варианте. Ну так вы же сами указали, что *  - т.е. все поддомены ссылаются на ваш сайт. А дальше все происходит так, как вы настроите:
для апача:<VirtualHost a.b.c.d:80>
ServerName site.ru
ServerAlias www.site.ru *.site.ru
...
</VirtualHost>
В этом варианте вы указали, что основное имя сайта - site.ru, но кроме него принимать запросы на www.site.ru и *.site.ru. Честно говоря www.site.ru в ServerAlias является излишним.
Т.е. любой поддомен вплоть до kfjjvkfjvbkjbvkjbvkjvbkejbv.site.ru приведет на ваш виртхост.
Если же в ServerAlias не указан *.site.ru - то произойдет следующее. Запрос придет на сервер, но подходящего виртхоста нет. Тогда апач отдаст этот запрос на обработку либо первому виртхосту в конфиге, либо так называемому default. Если админы хостинга не настроили default виртхост - значит отработает какой нить сайт с этого сервера.
Отсюда вывод - если уж вы указываете * IN A a.b.c.d в конфиге зоны - будьте добры корректно настроить виртхост - либо прописать *.site.ru в алиасе, либо создавайте для каждого нужного вам поддомена свой виртхост. Но это все равно не освободит вас от необходимости указать *.site.ru в алиасе какого нить своего виртхоста.
Не хотите такого поведения - прописывайте в настройках днс ровно те записи, которые вам нужны. Ну и виртхосты под них делайте.
Разница между прописыванием NS серверов и A записей - это просто место, где вы будете рулить доменом. Если вы перенесли NS сервера вашего домена на сервера хостинга - то необходимые записи в днс надо создавать в панели управления хостингом. Если же только A записи - то управление доменом остается у регистратора, а управление хостингом - у хостера.
что такое NS записи? разберитесь с терминами.
Правильно - А запись, чтобы по адресу mydomain.com вы попадали на нужный сервер (определялся верный IP)
NS-сервер в записи указывает на NS сервера, которые будут отвечать тем, кто будет искать mydomain.com
А то, что у вас apache на хостинге настроен криво, это уже другой вопрос. Apache поддерживает виртуальный хостинг, и на одном и том же IP могут висеть разные сайты. Как Apache настроен, так он и будет отвечать для неизвестных ему сайтов (выдавать дефолтный например)