On peut voir le script complet avec la requête? Merci d'avance

Je suppose que tu as testé sur une copie de la base de ton client.
Vérifie cependant que la "table op.parametrage" est bien conforme à ce que tu attends.
Le test du code retour donne quoi quand ça ne marche pas?

NB: J'espère que ta table "op.table_liste_codes" n'est pas très grande, parceque les temps de traitement des
clauses IN  et NOT IN risquent d'être particulièrement longs. Il faudrait peut-être optimiser un peu tout ça
NB2: C'est normal que tu ne testes pas "plan_comptable" à NULL?

Si tu places ta clause AND (plan_comptable = :ls_plan_comptable)
avant les clauses IN et NOT IN, est-ce que ça marche?

Fais un explain plan sur les deux versions de la requête.
Tu auras peut-être des surprises.

Chez le client, ils se connectent à la base via le driver natif Oracle, ou via ODBC?
Tu as fais une trace pour voir si, par hasard, la requête ne retourne pas un "No Data Found" chez le client?

Essaye cette requete, je pense qu'le va te donner un bien meilleur temps de réponse et un résultat correct :
  SELECT MAX (priorite) INTO :li_priorite_maxi
   FROM op.parametrage
   WHERE (portefeuille = :ls_portefeuille OR portefeuille IS NULL)
   AND (secteur_eco = :ls_secteur_eco OR secteur_eco IS NULL)
   AND (compte_actif = :ls_compte_actif OR compte_actif IS NULL)
   AND (classe_inventaire = :ls_classe_inventaire OR classe_inventaire IS NULL)       
   AND (categorie = :ls_categorie OR categorie IS NULL)
   AND (marche = :ls_marche OR marche IS NULL)
   AND (garantie = :ls_garantie OR garantie IS NULL)
   AND (plan_comptable = :ls_plan_comptable)
   AND (
          (
             pays_ocde = 'O' AND Exists (
                                           select 1
                                           from op.table_liste_codes
                                           where code = :ls_pays_ocde
                                           AND   num_table = :num_table
                                           AND   liste = :ls_ocde
                                           AND Rownum = 1
                                        )
          )
       OR (
             pays_ocde = 'N' AND Not Exists ( Select 1
                                              from op.table_liste_codes
                                              where code = :ls_pays_ocde
                                              AND  num_table = :num_table
                                              AND liste = :ls_ocde
                                              AND Rownum = 1 
                                            )
          )
       OR (pays_ocde IS NULL)
       )
;

J'oubliais ceci :
NVL(expr_1, expr_2)
Prend la valeur expr_1, sauf si expr_1 est NULL auquel cas NVL prend la valeur expr_2.
Une valeur NULL en SQL est une valeur non définie.
Lorsque l'un des termes d'une expression a la valeur NULL, l'expression entière prend la valeur NULL. D'autre part, un prédicat comportant une comparaison avec une expression ayant la valeur NULL prendra toujours la valeur faux. La fonction NVL permet de remplacer une valeur NULL par une valeur significative.
DE ce fait, je propose ceci : tu remplaces la clause

OR (pays_ocde IS NULL)
par ceci : OR (  NVL(pays_code,'XXX') = 'XXX' )

Et voilà, je pense que là ta requete est à la fois optimisé et doit répondre à tout ce dont tu as besoin.
A plus