Sure they do. I'm using a bunch of them right now. The only restriction startSSL has is that they don't accept popular names like 'amazon' or 'google' for subdomain names (I found out after I tried to get a cert for 'amazon.xxx.com' which we'd run in an AWS EC2 instance for testing). So we switched to 'sandbox.xxx.com' and got the cert within minutes.
They do, it's just that you cannot register a wildcard certificate for free. When I registered my certificate I could pick one subdomain in addition to the main domain.
