In the case of T9 (both directions) and going south on T16 you should request Oceanic clearance from Shanwick 30-90 minutes prior to boundary ETA. (I suspect Santa Maria will be similar in respect of NAVIX).
Oceanic Clearances should be requested at least 40 minutes before boundary ETO when entering Santa Maria airspace (via NAVIX, in this case).
Clearance request should comprise estimate for boundary position, requested level and mach no. and, in addition, the maximum level you are able to accept at the boundary. (Should your requested FL be unavailable, it's always good for ATC to know what you might accept as a higher alternative).
Definitely, additional information on the maximum flight level you're able to accept is more than welcome when requesting your oceanic clearance. Not only does it help on the planning, it will allow the controller to issue that clearance more expeditiously.
Cheers!