Is calls to the PersonalizedData.Load(Sid user) cached by EPiServer? We are planning on storing some metadata on users there, and it's important that it's "cheap" in terms of system resources to retrieve this information for any user (not only the currently logged in one).
No, PersonalizedData.Load() is not cached and will hit the database everytime its called.
EPiServer (4.x) do however cache UnifiedPrincipal's which in turn contains the PersonalizedData through the UserData property, and I suppose that you could try to retrieve the cached data through a call to UnifiedPrincipal.LoadFromCache(IIdentity).
If this calls fails, you could initialize the UnifiedPrincipal through the suitable constructor and then call AddToCache().