I do not see why it is a problem in the first place. BS answer. we set it for clients all the time upon request.
GS RichCopy 360 Enterprise - Voted #1 for data migration and replication in terms of performance and features. Replicate data across between servers in the same network, WAS, or even across the internet
How on earth could you patent a feature of an existing program? That's been in BIND forever. That would be like me patenting saving a file to disk or something.
Since I've not seen that patent enforced, and it definitely seems unenforceable, I think your host is being a bit silly about it. There are plenty of patents out there that you technically violate every single day, simply because they've not been thrown out yet.
Former owner of A Small Orange New owner of <COMING SOON>
Mosts hosts require you to have a unique ipaddress ($1 - $2/mo) if your account doesn't already have one. (Or if you want more than one wildcard)..
Other than that I've never heard of the Patent argument before. It shouldn't be hard to find a host that will let you do it.
Have you considered Semi-dedicated Hosting? 4 - 8 accounts per server. Less overhead than VPS, better performance for the price. DopeDomains.com - 15,000 New Domains a day. indexed by Pagerank, backlinks, Hits, and Length.
I think it's quite stupid to demand the Patent from the owner of the domain and I consider it's the right of the domain's owner to have wildcard entry in httpd conf. and DNS. If your host behaves like this then you have to think of its changing!!!