What does it mean to grant/set permissions for NETWORK SERVICE on a network share?
Solution 1:
NETWORK SERVICE is a well known account. It has the same SID on every machine. You are correct that NETWORK SERVICE on MachineA will not authenticate as NETWORK SERVICE on MachineB. It's not a group, it is an account.
It's very rare that you would be setting NETWORK SERVICE permission (share or NTFS) on a share. This would only be necessary if a service on the local machine, running under the credentials of NETWORK SERVICE, was trying to connect to that share on the local host.
When a service logging on as NETWORK SERVICE tries to connect to a remote machine the credentials of the local machine will be used. So if a service is running on MachineA in the domain example.com then that service would connect to MachineB as [email protected] (or example\MachineA if you like NetBIOS style names).