Since there appears to be positive feedback and interest in suggestion #2, I went ahead and prepared a list of the Kreis categories that will need to be created and those that need to be renamed. If there are any corrections or additions to this list, please reply to this answer. This does not mean suggestion #2 is certain, we will still need to submit it to G2G for a vote.
Create:
Kaliningrad Oblast
Darkehman (Kreis) (Russia), Ostpreußen
Friedland (Kreis) (Russia), Ostpreußen
Gerdauen (Kreis) (Russia), Ostpreußen
Gumbinnen (Kreis), Ostpreußen
Heiligenbeil (Kreis) (Russia), Ostpreußen
Insterburg (Kreis), Ostpreußen
Königsberg (Kreis), Ostpreußen
Labiau (Kreis), Ostpreußen
Pillkallen (Kreis), Ostpreußen
Preußisch Eylau (Kreis) (Russia), Ostpreußen
Ragnit (Kreis), Ostpreußen
Samland (Kreis), Ostpreußen
Stallupönen (Kreis), Ostpreußen
Tilsit (Kreis), Ostpreußen
Wehlau (Kreis), Ostpreußen
Goldap (Kreis) (Russia), Ostpreußen
Lithuania
Heydekrug (Kreis), Ostpreußen
Memel (Kreis), Ostpreußen
Rename:
Darkehman (Kreis) (Poland), Ostpreußen
Friedland (Kreis) (Poland), Ostpreußen
Gerdauen (Kreis) (Poland), Ostpreußen
Goldap (Kreis) (Poland), Ostpreußen
Heiligenbeil (Kreis) (Poland), Ostpreußen
Preußisch Eylau (Kreis) (Poland), Ostpreußen