fourier transform - Harmonic Product Spectrum limitations in pitch detection

I've made a pitch detection algorithm using HPS and I'm facing a problem. I'm a beginner with signal processing and this site helped me before, so I though I should ask.

For higher pitches ( eg. >C6:1046.50hz ) I'm starting to get garbage data from the HPS. The higher the pitch the more garbage I get (by garbage I mean frequencies that are not octave errors nor harmonics and are around 1Hz-20Hz)

What I've empirical observed:

1. 
   

   the results are worst for higher pitches, if the fundamental is above A6 or so, I get only garbage data.

   
   


2. 
   

   the FFT works fine even for a very high pitch, (by fine I mean that its peak shows either the fundamental or one of its harmonics, but not garbage)

   
   
   


3. 
   

   if I lower the number of harmonics I take in consideration for the HPS, the garbage diminishes, but that makes it harder to discriminate between the fundamental and the harmonics.

   
   

Here is my algorithm:

->raw buffer -> hann window, 16384 samples, 50% overlap -> zero padding -> FFT -> HPS

Any help is appreciated!

UPDATE 1: So, there are a few more things I want to add:

1. The sample rate I'm recording at is 44100 Hz


2. I've observed that this behavior is barely visible on a guitar, but very visible on an digital piano (for the same played note)


3. 
   

   Here is my hps algorithm, maybe someone with greater experience can spot a problem.

   
   

   int hps(float* spectrum, int spectrumSize, int harmonics) {
   
   int i, j, maxSearchIndex, maxBin;
   maxSearchIndex = spectrumSize/harmonics;
   
   maxBin = 1;
   
   for (j=1; j<=maxSearchIndex; j++) {
       for (i=1; i<=harmonics; i++) { 
           spectrum[j] *= spectrum[j*i];
       }
       if (spectrum[j] > spectrum[maxBin]) {
           maxBin = j;
       }
   }
   
   // Fixing octave too high errors    
   
   int correctMaxBin = 1;
   int maxsearch = maxBin * 3 / 4;
   for (i=2; i    if (spectrum[i] > spectrum[correctMaxBin]) {
           correctMaxBin = i;
       }
   }
   if (abs(correctMaxBin * 2 - maxBin) < 4) {
       if (spectrum[correctMaxBin]/spectrum[maxBin] > 0.2) {
           maxBin = correctMaxBin;
   
       }
   }
   
   return maxBin;
   }