Ok, I've solved this one myself.
Whether a user actually exists isn't checked until after all checks in 'smtpd_recipient_restrictions' have been done and returned OK, PERMIT or DUNNO.
To force this check to be performed earlier you need to add 'check_recipient_maps' into 'smtpd_recipient_restrictions'.
My 'smtpd_recipient_restrictions' now looks like:
smtpd_recipient_restrictions = permit_mynetworks,
I haven't seen this ever mentioned in any Grey listing documentation, but is seems fairly significant to me as the load saving on grey listing is fairly large.
Hope this info is helpful.