It's not the phone that does the penetrating, it's the type and strength of the radio waves being transmitted by the source tower. The radio receiver in the phone has a property called "sensitivity" that helps determine how well it captures the transmitted signal. It's kind of like people whose hearing is better than others. Some people choose to listen to a radio or TV at a certain volume; others in the same room can't make out words being said because they claim it isn't loud enough. Sort of the same with phones, or any radio receiver.
The fact that you mentioned your old Verizon phone brings up that most likely in that area, VZW (Verizon Wireless) uses 850 Mhz service, as opposed to their other option, service at 1900 Mhz (which is commonly referred to as the PCS band). 850 Mhz radio waves tend to penetrate structures better than 1900 Mhz waves. Even outdoors in the clear, one watt of transmitted 850 will "travel farther" than one watt of transmitted 1900. Thus all the conversations and hubbub about obtaining valuable radio spectrum for use with whichever company.
For coverage's sake, different strategies are used by a cell company depending on what type of signal they have to work with. Some companies have primarily only 1900 Mhz to work with (Sprint IIRC, T-Mobile), others have both (most of the others), but what is used in a given area depends on their individual licenses that they bought and paid for, usually in what's known as a spectrum auction.
This is in reference mainly to 2G signal. Some cell companies use even different frequencies for their 3G and newer generation services (some companies are obtaining the right to use 700 Mhz, for instance), and this will follow the same principles of radio as previously stated.
All that being said, yes, some phones of a given carrier and service type will outperform others. Some are just lucky in that they're designed with this or that part located in a certain area of the phone, like the antenna at the top instead of the bottom (where your hand often covers it), or even simple issues like quality control of parts or how they're tweaked before they leave the factory.
So it's essentially trial and error, personal experience reports, etc. You'd have to have all your buddies with different phones stand in the same place in the Target and give signal reports and see who gets the best signal. Some phones do have a reputation as being signal kings, but even that can vary between different samples.
Regarding your T-Mobile phone, it could be a combination of elements making your signal weak at that point in the store. First, they're likely using a 1900 Mhz signal (unless we're talking 3G); or the cell tower could be further away than the VZW one that hits the same store, thus making their signal weaker. You can't really put it in terms of, "is this a common problem with T-Mobile" kind of thing. There are the variables to consider.