Логически следовало бы заключать в кавычки так называемые вторичные названия, т.е. такие, которые не возникли в силу естественной территориальной привязки (как, скажем, Приокско-Террасный заповедник), а присвоены парку как некоему аттракциону или спортивно-развлекательному комплексу (подобно кинотеатру или стадиону). О «вторичности» тут можно говорить потому, что для таких названий часто берутся топонимы, принадлежащие другим географическим объектам. Посудите сами: если взять приведённое Вами же название сад «Нева», ну разве тут можно убрать кавычки? Ведь Нева — это река, а не сад, оттого и кавычки. Точно так же нужны кавычки и в названии парк «Сокольники», потому что изначально Сокольники — название деревни (а сейчас, если не ошибаюсь, микрорайона). Я бы брал в кавычки и иностранные названия, например национальный парк «Эверглейдс» (хотя это название и совпадает с естественным топонимом — обозначением болотистой местности во Флориде, но тоже является вторичным, потому что сам парк охватывает только часть этой территории).

В то же время Вы правы, отмечая, что, если название синтаксически сочетается с родовым словом, то кавычки не нужны (Сокольнический парк).

Само словосочетание национальный парк в общем случае следует писать со строчной буквы. Прописная буква уместна в юридически значимых контекстах, когда национальный парк рассматривается как юридическое лицо, название организации, совершающей какие-то действия (например: «29 августа Калининградский зоопарк и Национальный парк "Куршская коса" присоединятся к Всероссийской экологической акции»).