Is there any way for me to get a wildcard effect using zoneedit?

Hmm...I used zoneedit at one time, but cannot remember. Im not sure if any of the free DNS services provide wildcards, as I know for a fact mydomain.com does not.

as I know for a fact mydomain.com does not.
mydomain.com does allow wildcards if you are on the MyDNS service, I have it set up on a few of my domains actually...

if you click the link to Add a Subdomain/Hostname...
enter * for the Host Name
Select IP pointing...
then add the IP you would like to use for the domain wildcard... worked for me, should work for you :stickout
a few months ago this wasn't possible, it is now

Cool! flamethrow (love this emoticon)

Havent been in my control panel in mydomain.com in a while :) You can tell :)

If my server is name-based(where other domains are also hosted on it) will your method still work?

You should point the wildcard to the IP address of the server and set up the subdomains using the server IP and you should be good to go.