URL Redirect created over SSL only works over SSL
I am feeling a little sheepish here:

Caching was turned on for anonymous users. When accessing the site as https I was also logged into Drupal, unlike when I was accessing the site over http. 

As such the anonymous users were not getting the redirect or alias applied until the cache was cleared. Should have been an obvious first step.