I have written a windows service that runs under the Network Service account. The application is to receive messages from MSMQ residing on another server. Without the windows service wrapper around the app, the actual receiving of the queue works fine. So I know it's something to do with the account, aside from the MSMQ service raising an Access Denied error. Within MSMQ itself and the specific queue that my service is interested in I have ensured for now at both levels the Network Service Account has full control of the queue, so I dont understand why I'm still receiving access denied errors.
I needed a user in the Active Directory with appropriate permissions. This user also had to be given correct permissions on the MSMQ Service.