Membership and Authentication have nothing to do with each other (well, almost nothing). Request.IsAuthenticated merely means that there is a valid FormsAuthentication cookie on the browsers computer. It has nothing to do with getting the Membership information, other than by providing the correct IIdentity.Name value.
It seems likely that the issue here is in your Membership provider. You mention that you use a web service to retrieve membership information. You say that you've eliminated that as a source of the problem, but don't say how you've eliminated it.
I would say it's highly likely related to this webservice.