The button seems to be added only "later" on, after even DOMContentLoaded has fired. I get your script to work consistently by using sleep 1 to give the page more time to construct itself:

use strict;
use warnings;
#use local::lib;
use WWW::Mechanize::Firefox;
warn $WWW::Mechanize::Firefox::VERSION;

my $mech = WWW::Mechanize::Firefox->new(
    autoclose => 0,
    autodie => 1,
);
$mech->get('http://www.rightmove.co.uk/');
# Filling in and submitting the first forms works:
$mech->submit_form(
                   with_fields => {
                                   searchLocation => 'N1',
                                  }
                  );

sleep 1; # give the page more time
$mech->click({xpath => '//*[@id="submit"]'});
[download]

To make this truely robust, you would need to wait (always with a timeout!) until the search button becomes visible:

my $retries = 10;
while ($retries-- and ! $mech->is_visible( xpath => '//*[@id="submit"]
+' )) {
      sleep 1;
};
die "Timeout" unless $retries;
[download]