Billy Leslie is still (I believe) a NAUI instructor, and is now working somewhere up north (I'm not sure where). I have often conducted certifying dives for NAUI students even though I'm not a NAUI instructor, with the full knowledge and approval of NAUI. There are a few minor differences from the PADI dives and NAUI are happy to give instructions to a non-NAUI instructor. Only a NAUI instructor can sign you off at the end and issue your certification, so once the dives are completed you go back to him/her for the final stage.
And yes, I've seen Carlos at AD. They now have two locations, their original one at Sunbreeze Hotel and now an additional site at Journey's End, and I don't know where he is to be found.