_nic, вы вот код не приводите и приходиться заниматься построением гипотез.

Вероятно, есть подключи

http://msdn.microsoft.com/en-us/library/ms724235(VS.85).aspx

вот тут "Deleting a Key with Subkeys"

И еще в качестве второго параметра RegDeleteKey у вас что?

Впредь, задавайте вопросы корректно. Давайте максимум информации (что вернула GetLastError - в данном случае regdeletekey сама возвращает код ошибки- и приводите кусок бажного кода обязательно). Время и свое сэкономите и тех, кто отвечает.