Is it possible for a published paper with PMID to not have a PMCID?
PMIDs are given to any paper indexed in the pubmed citation database, and that is any paper in a journal indexed by pubmed. Which is pretty much all reputable journals more than a couple of years old. 

PMCIDs are given to papers where a copy of the paper is availible on Pubmed Central. While pubmed and pubmed central have similar names, they are not the same thing.  Pubmed Central is a government run archive service for manuscripts openly accessible to the public. Different journals have different policies on allowing authors to archive copies of the manuscripts on public servers (like Pubmed central). Open Access journals allow archiving. Many closed access journals allow archiving after a certain period, or on payment of a fee. Allowing archiving is not the same as doing it though. While some journals that allow it will go as far as automatically uploading papers in mnay cases its something the author has to do themsevlves. I believe that that NIH requires research funded by them to be uploaded to PMC within 6 months of publication, but the NIH doesn't fund all research in the world. Many european funders, for example, either don't have a archiving requirment, or do, but don't specify pubmed central as the archive (other archives are available).