А>Дело в том, что даже при запуске сервиса от имени определенного юзера, все равно выдается ошибка "соединение не найдено в phonebook",

Странно.

А>Где эти загадочные "телефонные книги"...

Windows XP:

C:\Documents and Settings\<UserName>\Application Data\Microsoft\Network\Connections\Pbk\*.pbk

Windows Vista и выше:

C:\Users\<UserName>\AppData\Roaming\Microsoft\Network\Connections\Pbk\*.pbk

При этом если запись при создании была сделала "общей", то в качестве <UserName> следует подставить "All Users".

А>Как указать конкретную phonebook при вызове RasDial?

RasDial():

lpszPhonebook [in]
Pointer to a null-terminated string that specifies the full path and file name of a phone-book (PBK) file. If this parameter is NULL, the function uses the current default phone-book file. The default phone-book file is the one selected by the user in the User Preferences property sheet of the Dial-Up Networking dialog box.