Has anyone had experience of getting SFDC to provision licences directly to a sandbox without the need to refresh the box from production?
I'm pretty sure this can't be done. At least not for license seats. It might be possible for feature licenses. All I can suggest is to contact your AE for help.