You have to do this with NTFS permissions, not share permissions because share permissions aren't granular enough. (I almost always have the trivial access control list of Everyone:Full Control for share permissions). Grant Write, Read and Execute, and List on the directory. This allows the addition of new files, but not their deletion.

There are 2 wrinkles:
1. Users can modify these created files, but you said "...renames or deletes..."--would modifying the file also be a problem? If so, then I suspect that this can still be solved on 2k/XP with inheritable permissions but I don't know for sure.

2. The owner of a file has an irrevokable Change Permissions right. Therefore, whoever creates a file can set whatever permissions they want.

RunAs is a possiblilty, but there is nothing like suid root. I haven't tried invoking a shell from VB using runas--I think I see an experiment this afternoon.