S’agissant de la fonction, il me semble en effet que « Premier » doit prendre la majuscule, peu importe qu’il n’y ait pas de titulaire désigné.
La logique est de distinguer l’institution de l’expression constituée d’un adjectif ordinal (premier) et d’un nom commun. Untel est le premier ministre à avoir démissionné pour abus de drogues. 
De même, les institutions prennent une majuscule : le Gouvernement, le ministère des Armées, le Sénat, l’Assemblée nationale.

Les habitudes, parfois très implantées, finissent par faire perdre de vue les principes typographiques. La majuscule s’applique normalement à un nom commun qui prend une valeur absolue, donc qualifiant un objet unique et parfaitement identifiable : personne physique, lieu précis, période historique, etc. Cela suppose le singulier et l’article défini.
En l’espèce, il faut donc distinguer :
– le poste de premier ministre (de premier des ministres) qui est commun et sans majuscule ;
– la personne qui porte ce titre à un moment donné et dans un contexte précis.
Cela donne donc : 
– La Ve République a connu des dizaines de premiers ministres (pluriel) ou Ce n’est pas un premier ministre qui décide de cela (article indéfini). 
– Le Premier Ministre inaugurera le musée la semaine prochaine (on connait son identité, monsieur X ou madame Y, l’appellation vaut nom propre). 
À noter que le mot ministre est souvent laissé, contre toute logique, sans majuscule. La norme est pourtant que c’est le substantif qui porte la majuscule, ainsi que l’adjectif qui le précède le cas échéant. 
L’avantage de ce principe est qu’il s’applique à tous les titres, simples ou composés : le Président se différencie d’un président de la République si le contexte est sans équivoque et le Maire se justifie dans un conseil municipal donné à la différence des maires des 35 000 communes de France.