If you are going to use the four argument credentials, you need to pass the right data into it. Location is <host>:<port> as documented in LWP::UserAgent.
Try this totally untested piece of code and see if you get better results.
my $mech = WWW::Mechanize->new();
# Don't pass the full URL as the location in the call to credentials!
my $server = 'api.datamarket.azure.com';
my $url = "https://$server/Bing/SearchWeb/Web?Query=%27Xbox%27&$top=1
my $loc = "$server:443";
my $account_key = "<my key>";
# Yes, WWW::Mech still supports LWP::UserAgent's four arg credentials
$mech->credentials($loc, '', '', $account_key);
Update: After I posted this, I realized that you were using https so I updated the port from 80 to 443.