Basically is there a call I can make through the GP web services to retrieve what companies a user has access to within Great Plains?
Yes, I believe I'm able to simply cycle through my list of users and make the GetCompanyList call for each user using the WorkOnBehalfOf property of the Context. A bit tedious and potentially a lot of heavy web service calls but I don't believe GP exposes any other way to do this.