I have an answer to my mystery.
The problem was in the definition of the module B's packaging. It was:
  <build>
    <plugins>
      <plugin>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-maven-plugin</artifactId>
      </plugin>
      <plugin>
        <groupId>org.apache.maven.plugins</groupId>
        <artifactId>maven-surefire-plugin</artifactId>
      </plugin>
    </plugins>
  </build>
So, the problem was that spring-boot-maven-plugin produces Fat Jar (executable) and basically has different structure that a plain library.
The package that I needed was unpacked to:
BOOT-INF/classes/my/needed/class/Clazz.class
instead of
my/needed/class/Clazz.class
at the root level as in a regular Jar.
Interestingly, IntelliJ was fine with both.
The solution would be to move the common classes to module C which acts like a library, which will sadly require quite a lot of effort, but at least my mystery is resolved now.