The PartCreationPolicy should go on the class, even if the export goes on the property. The class is what corresponds to the part, and the creation policy will control whether MEF creates a new instance of the class each time an export is requested from it or not.
I am not sure whether you want to use Shared or NonShared. You have the CreationPolicy set to Shared in your code example, but then you are creating a new instance of MyService in your property getter. That seems to indicate you may be looking for a creation policy of NonShared.
If you do want a new service to be created each time an export is requested, you should do it via the creation policy, and not by creating a new instance in the getter. The value of an export is not supposed to change at runtime, and in fact MEF will only call the getter once, and store the return value for when it needs to access the exported value again. So creating a new instance in your getter can make it look like there would be multiple services created when there will actually only be one.