Don't worry about DNS and URL rewriting
Your DNS record will be static, something like:
*.YOURDOMAIN.COM A 123.123.123.123
Ask your DNS provider to do it for you (if it's not done already) or do it by yourself if you have control over your DNS records. This will automatically point all your subdomains (current and future ones) into the same HTTP server.
Once it's done, you will only need to parse HOST header on every single http request to detect what hostname was used to access your server-side scripts on your http server.
Assuming you're using ASP.NET, this is kind of silly example I came up with but works and demonstrates simplicity of this approach:
<%@ Language="C#" %>
<%
string subDomain = Request.Url.Host.Split('.')[0].ToUpper();
if (subDomain == "CLIENTXXX") Response.Write("Hello CLIENTXXX, your secret number is 33");
else if (subDomain == "CLIENTYYY") Response.Write("Hello CLIENTYYY, your secret number is 44");
else Response.Write(subDomain+" doesn't exist");
%>