I ended up using a Session variable to temporarily store the postal-code - by hooking into the RecordService.RecordPartiallySubmitted event.

public class AppStart : ApplicationEventHandler
{
    protected override void ApplicationStarted(UmbracoApplicationBase umbracoApplication, ApplicationContext applicationContext)
    {
        base.ApplicationStarted(umbracoApplication, applicationContext);

        RecordService.RecordPartiallySubmitted += RecordService_RecordPartiallySubmitted;
    }

    private void RecordService_RecordPartiallySubmitted(object sender, RecordEventArgs e)
    {
        var zipcode = e.Context.Request["ca5d8e93-244c-4fc4-ba34-ee9c4dcc9413"];

        if (!string.IsNullOrWhiteSpace(zipcode))
            e.Context.Session.Add("zipcode", zipcode);
    }
}

(I used the Request object directly here - but I could have checked the e.Record.RecordFields to get the same value)

Then have a custom FieldPreValueSourceType to pick up the Session variable.

public class MyCustomPrevalueSourceType : FieldPreValueSourceType
{
    // <snip>

    public override List<PreValue> GetPreValues(Field field)
    {
        var zipcode = UmbracoContext.Current.HttpContext.Session["zipcode"].ToString();
        if (!string.IsNullOrWhiteSpace(zipcode))
        {
            var dates = GetTheScheduledDatesFromTheWebService_GoGoGo(zipcode);
            if (dates != null)
            {
                return dates
                    .Select((x, i) => new PreValue()
                        {
                            Field = field != null ? field.Id : Guid.Empty,
                            Id = x.Id,
                            SortOrder = i,
                            Value = x.Value
                        })
                    .ToList();
            }
        }

        return new List<PreValue>();
    }

    // <snip>
}

Hope that helps if anyone else wants to do similar.

Cheers,
- Lee