I just wanted to post something...
I struggled with a similar issue where the 'Record' option was greyed out, despite the fact that 'Meeting recording' was toggled on under 'Meeting policies'. In Teams, when mousing over the greyed out 'Start recording', it said 'Only people designated by admin policy can start recording'.
What I realized is 'Meeting policies' only applies to Teams MEETINGS. If I manually 'video call' someone, that's not technically a meeting, but rather a call. Thus, I needed to enable 'Cloud recording for calling', which is under 'Calling policies'. Within the hour, the 'recording' option was available for video calls. This makes total sense, just didn't think about it in terms of two distinct policies.
Not sure this is the relevant thread, but wanted to post my experience.
JMM