La pseudo classe :first-child tiene conto solamente della caratteristica gerarchica degli elementi in questione, per cui va a selezionare il primo tra gli elementi figli, a prescindere dalle classi ad essi applicate (o non applicate).
Quindi, in questo caso, quel :not(.hide) non ha alcun valore ai fini della selezione effettuata dal :first-child, che va a selezionare comunque il primo figlio dell'elemento contenitore; anzi con quel :not() sarà addirittura escluso, dalla selezione, anche quel primo figlio perché appunto ha applicata la classe .hide.
Morale della favola: quel selettore non selezionerà alcunché in un caso del genere.

Per come l'hai impostata, ti ci vorrebbe un selettore del tipo :first-of-class, il quale attualmente non esiste.

Si può comunque risolvere diversamente per ottenere ciò che hai chiesto.
Esempio:
codice:
<!DOCTYPE HTML>
<html>
  <head>
    <title>Esempio</title>
    <meta charset="utf-8">
    <style type="text/css">
      .container .item:not(.hide)+.item /* questo applica il bordo solo a .item 4 e quelli seguenti */
      /*,.container .item.hide*/ /* decommenta questo se ti serve che anche gli .hide abbiano il bordo */
      {border:1px solid #000}
      
      .hide{display:none}
    </style>
  </head>
  <body>
    <div class="container">
      <div class="item hide">1</div>
      <div class="item hide">2</div>
      <div class="item">3</div>
      <div class="item">4</div>
    </div>
  </body>
</html>
Chiaramente questo è valido per l'esempio che tu stesso hai riportato, ma potrebbe non essere adatto in altri casi.
Supponiamo ad esempio questo:
codice:
<div class="container">
  <div class="item hide">1</div>
  <div class="item hide">2</div>
  <div class="item">3</div>
  <div class="item">4</div>
  <div class="item hide">5</div>
  <div class="item">6</div>
  <div class="item">7</div>
</div>
Il bordo è applicato ai div 4 e 7, perché sono considerati quelli che seguono un .item dopo qualsiasi .hide. Restano quindi esclusi il 3 e il 6. Infatti, ovviamente, il 3 non è il solo primo .item dopo un qualsiasi .hide, ma dalle tue indicazioni non è chiaro se puoi avere delle situazioni in cui gli .hide siano sparsi oppure puoi averli solo come elementi iniziali.

Vedi un po' se è sufficiente come soluzione, altrimenti chiarisci meglio specificando eventuali altre situazioni che ti si possono presentare e fornendo tutti i dettagli del caso.