The alternative version, using rewrite and proxy_pass behaved perfectly - the problem was the other server returning 200's instead of 404's. So for completeness, here is the working config:

server {
   listen 80;
   server_name localhost;
   error_log  /tmp/nginx.error.log notice;
   access_log   /tmp/nginx.access.log;
   location /tile/SteveCountryVic/ {
        rewrite_log on;
        rewrite ^.*/(\d+)/(\d+)/(\d+.*)$ /$1/$2/$3 break;

        proxy_intercept_errors on;
        error_page 404 = @dynamiccycletour;
        proxy_set_header Host $http_host;
        proxy_pass http://127.0.0.1:5005;
  }

   location @dynamiccycletour {
        rewrite_log on;
        rewrite ^/(\d+)/(\d+)/(\d+.*)$ /tile/SteveCountryVic/$1/$2/$3 break;
        proxy_pass http://115.x.x.x:20008;

   }

first thing you haven't set your root - directive correctly -> thats why you get a 404 -> thats why all requests are redirected to your @dynamiccycletour (openstreetmap?)

btw, whats the difference between /tile/ and /tile/SteveCountryVic/ ?

so we need a little cleanup here first:

server {
   ....
   # define where to find files 
   # be sure to have it like /path/to/tile
   root /path/to/tiles/;


   location /tile/SteveCountryVic/ {

       # if file not found -> remote server
       try_files $uri @dynamiccycletour

        rewrite_log on;        
        # this should cover /1/2/3.png. no?
        rewrite /tile/SteveCountryVic/(.*).png$ /$1.png break;

        # i'm not sure this will match due the the rewrite
        proxy_redirect /tile/SteveCountryVic/ http://localhost:5005/;


   location @dynamiccycletour {
        rewrite_log on;

        # this should cover /1/2/3.png. no?
        rewrite /tile/SteveCountryVic/(.*).png$ /$1.png break;
        proxy_pass http://115.x.x.x:20008;


   }

 }