aptitude search says "package will be installed"

[Dalios <dalios@eumx.net>]

Hi all,

A few weeks back while I was still following Stable (wheezy) I used 
gdebi to install a package (minitube if that matters). Later I upgraded 
to Testing (jessie) and now I used the command "apt-get purge minitube" 
to uninstall the package but when I use the command "aptitude search 
minitube" the return i get is:

pi  minitube          - Native YouTube client

According to the aptitude's man page as well as aptitude user's manual 
(http://algebraicthunk.net/~dburrows/projects/aptitude/doc/en/index.html) the 
first 2 letters of that line mean:
p: no trace of the package exists on the system
i: the package will be installed

What does that "the package will be installed" mean? When will it be 
installed?

Note that I have already tried the commands:
     apt-get install -f
     apt-get clean
     apt-get autoclean
     apt-get autoremove
     apt-get update && apt-get upgrade && apt-get dist-upgrade

and nothing changed.

Is this a problem because of using gdebi? Is this because I used apt-get 
to uninstall and aptitude didn't get the memo?

Thanks in advance,
Dalios