So, bei All-Inkl musste nun eine Wildcard Subdomain (oder so ähnlich) angelegt werden. Diese heißt einfach "*.meinedomain.de" und zeigt auf das root-Verzeichnis des Servers. Ein paar Minuten warten, bis die Änderungen aktiv sind und schon hat es funktioniert.
Wildcard Subdomains sind meines Wissens nach aber nicht in jedem Tarif enthalten. Müsste also vorher abgeklärt werden.
Ich hoffe, ich konnte dem ein oder anderen Helfen!