Answer
Gp.CheckProduct() is used to determine if a license has been purchased, not if free licenses are available. For example, if three floating ArcInfo licenses are present and they are all being used by other users, Gp.CheckProduct("ArcInfo") still returns 'Available'. This means that ArcInfo has been purchased and is theoretically available, not that there are free licenses available. At this time, there is no geoprocessing method to determine if there are any free licenses.