Veja o uso de CNAME's. Fazer com que os usuários criem CNAMEs personalizados em seus registros DNS e fazer com que seu site tente acessá-los é uma forma de verificar a propriedade de um domínio.

Outro seria um pouco mais de trabalho, mas fazer com que os usuários adicionem uma meta tag ao site e, novamente, sua página tente acessar e ler essas informações Meta para provar que eles têm acesso à página - verificando assim a propriedade.

ATUALIZAR:

dns-get-record

Consulte AQUI a documentação PHP sobre como obter e verificar os registros DNS (CNAME sendo um destes)