I'm using the albumId that I got from the albums.list method. It is, in my eyes, a valid ID, because I can use the albums.get method to get the album.
I'm using the mediaItemId that I got from the mediaItems.list method. It is, again in my eyes, a valid ID, because i can use the mediaItems.get method to get the mediaItem.
Both work without problems!
When I'm trying to add the mediaItem to the album, using the albums.batchAddMediaItems method, I get an
error: No permission to add media items to this album.

I used OAuth 2.0 and checked every scope that can be checked.