As for Provinces - keep in mind that calling many of imperial lands "vassal" wasn't a case before adaptations, the only officialy neutral realm was Ebbing. Maecht, though being a kingdom ruled by a king, is inside the Empire's borders, clearly indicated in the moment when Skellen's gang crosses Maecht-Ebbing border.
In this case, I think the Empire can be divided in huge blocks called Provinces, which are traditionally divided in various kingdoms and duchies, and technically in Palatinates. Palatinates are mentioned in the books though no land has been referred to as a palatinate yet, aside from Caldwell being called the Palatine (Palatinate of Lyria and Angren then? With Villem as traditional ruler and Caldwell as the technical one?)