In order for Record Validation to work correctly, you will need to grant your users access to all RV Apex classes. There are two possible ways to go about this. You can allow access to certain user profiles, or assign our permission set to individual users.
The advantage of using the Permission Set is that RV can update the set externally. Therefore you don't need to make any changes after future updates where new classes might be introduced. If you don't want your users to access certain RV pages, for example, RV Setup, choose the User Profile option. You can then manually decide which pages your user can access by choosing the right Visualforce Pages.
Option 1: Allow access to a user profile