I finally found the answer to this and it was so simple!! (He says after hours of searching and debugging).
I just had to tell explicitly say in which assembly my custom provider resided. I thought I only had to do this when specifying the type when adding the provider.
However you need to define when defining your profile in the inherits attribute. Like so:
Before:
<profile defaultProvider="MyCompanyProfileProvider" inherits="MyCompany.Web.User.GenericProfile, automaticSaveEnabled="false">
After:
<profile defaultProvider="MyCompanyProfileProvider" inherits="MyCompany.Web.User.GenericProfile, MyCompany.Web" automaticSaveEnabled="false">
Hope this helps somebody else in the future with the same problem.