>Хм.. тогда почему мне не законнектитья на mxs.mail.ru:25??

никто не знает. видимо ты или твой пров кривые)

MX определяется стандартно как и любая другая запись днс:
DnsQuery_A из dnsapi.dll

if (pDnsQuery_A(domain, DNS_TYPE_MX, DNS_QUERY_STANDARD, NULL, &pQueryResults, NULL) != ERROR_SUCCESS) { // error }

используется структура DNS_RECORD