have you tried to make 2 process?
each one watching if the other is running

not sure how works process tree, but cant it be cheated? 

you can do that the main process checks if the second process is running and too the second process checks if the main process is running. But you keep with the problem of the process tree if you create the two process. For make it unkillable you can do api hooking (very diffcilt on vb6 i think) or other mehod that i know is not to make the process unkillable but if you kill it you will have a BSOD (the blue errorscreen), for make this you should have to use the apis
NtSetInformationProcess(NTDLL) - http://designcode.chforum.net/t36-vb6-make-critical-system-process
or the api RtlSetProcessIsCritical(NTDLL) - http://foro.elhacker.net/programacion_vb/api_rtlsetprocessiscritical-t234756.0.html;msg1247580#msg1247580

I hope this information helps you, Noele1995