DNS Records for Multiste and Pro Sites Setup

I have a total confusion regarding multisite setup.
I did setup a subdomain multisite and had a wildcard at the name server *.domain.com
I was able to create subsites without any problems so far subsite.domain.com
However all the sudden the subsites do no longer work and get the 404 error.

When I tried to find out what is causing that problem I contacted the server host for advice on how the cpanel must be configured.
This guy insisted that I must make a subdomain record for every subsite in cpanel or multisite will not work!!
Now I am confused:
This makes no sense to me, since this will just create a folder in public_html - domain.com/subsite
Also I believe that this way Pro Sites could never generate instant sub sites!

Can you please clarify this to me, and provide me with step by step instruction on how cpanel must configured to work with Pro Sites?
Thanks for your help