The things you learn when you're bored at work... :)
Never did anything with sockets or AnyEvent before, but here it goes.
After getting the latest AnyEvent (v5.24 is incompatible with AnyEvent::Handle::UDP v0.033) and AnyEvent::Handle::UDP packages from CPAN, this code seems to work:

#!/usr/bin/perl

use strict;
use warnings;
use AnyEvent;
#use AnyEvent::DNS;
use AnyEvent::Handle::UDP;
use AnyEvent::Socket ();
use Socket;
use Net::DNS::Packet;
use Data::Dump;

my $cb = sub {};

my($proto) = shift;

my $fqdn = "$proto.local";
#my $data = AnyEvent::DNS::dns_pack { rd => 1, qd => [[$fqdn, "ptr"]] 
+};
my $d = Net::DNS::Packet->new($fqdn, "PTR");
my $data = $d->data;

my %found;
my $callback = sub {};

my $cv_recv = AnyEvent->condvar;

my $t;
$t = AnyEvent::Handle::UDP->new(
#    fh => $sock,
    #bind => ['0.0.0.0', 5353],
    timeout => 3,
    on_timeout => sub {
print STDERR "WTF? timeout...\n";
        #undef $t;
        #$cb->(values %found);
    },
    on_error => sub {
print STDERR "An error has occurred:";
        Data::Dump::dd(@_);
    },
    on_recv => sub {
print STDERR "callback!!\n";
        my $buf = shift;
        my $handle = shift;
        my ($res,$err) = Net::DNS::Packet->new(\$buf, 1);

        my @rr  = grep { lc $_->[0] eq $fqdn && $_->[1] eq 'ptr' } @{ 
+$res->{an} };
        my @srv = grep { $_->[1] eq 'srv' } @{$res->{ar}};

        if (@rr == 1 && @srv == 1) {
            my $name = $rr[0]->[3];
            $name =~ s/\.$fqdn$//;

            my $service = {
                name => $name,
                host => $srv[0]->[6],
                port => $srv[0]->[5],
                proto => $proto,
            };

            $found{$rr[0]->[3]} ||= do {
                $callback->($service) if $callback;
                $service;
            };
        }
        $cv_recv->send;
    },
);

#$t->bind_to(pack_sockaddr_in(0, Socket::inet_aton('0.0.0.0'))); # Doe
+s not work for some reason
$t->bind_to(['0.0.0.0',0]);
my $cv_send = $t->push_send($data, pack_sockaddr_in(53, Socket::inet_a
+ton('IP_OF_DNS-SERVER_HERE')));
print("Waiting for data to be sent...");
$cv_send->recv;
print("[OK]\n");

print("Waiting for data to arrive...");
$cv_recv->recv;
print("[OK]\n");
[download]

Output:

me@server:~/testscripts$ ./monks17.pl localhost
Waiting for data to be sent...[OK]
callback!!
Waiting for data to arrive...;; HEADER SECTION
;; id = 32508
;; qr = 1    opcode = QUERY    aa = 0    tc = 0    rd = 1
;; ra = 1    ad = 0    cd = 0    rcode  = NXDOMAIN
;; qdcount = 1  ancount = 0  nscount = 1  arcount = 0

;; QUESTION SECTION (1 record)
;; localhost.local.     IN      PTR

;; ANSWER SECTION (0 records)

;; AUTHORITY SECTION (1 record)
.       900     IN      SOA     a.root-servers.net. nstld.verisign-grs
+.com. (
                                        2012042600      ; Serial
                                        1800    ; Refresh
                                        900     ; Retry
                                        604800  ; Expire
                                        86400 ) ; Minimum TTL

;; ADDITIONAL SECTION (0 records)

[OK]
me@server:~/testscripts$
[download]