I think that your intuition regarding the concepts of common support and matching is correct.
Having said that, I think we need to fully appreciate what "with replacement" entails. Let's consider what will happen in the case of two sample that do not have substantial common support: When matching with replacement a lot of instances from the treatment group can be matched to the same instance from the control group. That is because the same control instance can be the nearest neighbour for many treatment instances. As the NSW sample and the PSID sample have a small overlap regarding their pre-treatment characteristics this translates into not having a lot of unique control samples picked. To that extent, yes, if we are using 1-to-1 matching with replacement we cannot ever have more control samples picked than the number of treatment samples.
One the other hand, with caliper matching we will use all of the control units within a pre-defined propensity score radius (the caliper). In that sense, a larger sample size is not unexpected. Note that caliper matching is far from a silver-bullet. Some treatment units may not receive any matches because there are no neighbours within the given caliper. As Morgan & Winship, propose in Chapt. 5 you might be better to "use a hybrid approach, where in a second step all treatment cases without any caliper-based matches are then matched to a single nearest neighbor outside of the caliper."
I do not have access to Stata, but assuming you can use R's MatchIt package, you can compare the output of:
out1 <- matchit(treat ~ re74 + re75 + educ + black + hispan + age,
data = lalonde, method = "nearest", replace = TRUE)
out2 <- matchit(treat ~ re74 + re75 + educ + black + hispan + age,
data = lalonde, method = "nearest", replace = FALSE)
In out1 we use 1-NN matching with replacement and then out2 1-NN matching without replacement. The matched dataset created by out2 is smaller than out1 exactly because a number of control subjects are reused. (The data lalonde is a subsample from the NSW study.)
In general, be skeptical towards procedures that remove data aggressively.
Finally, you are right to question the actual numbers reported in the paper. I think the wording leaves something to be desired. By 56 the authors most probably denote the number of matched control units, rather than "No. of observations" which itself is unambiguiduous if it refers to the whole matched sample or just the treatment sample of it.
Unfortunately I cannot replicate exactly because I do not have the full dataset; the unemployment figures are provided by the authors. I can replicate the analysis without these figures in which case they are 66 (not 56) matched control units against 185 treatment units. So 56, while quite low is not totally improbable. I attach the R code used below:
rm(list=ls())
NSW = read.table('http://www.nber.org/~rdehejia/data/nswre74_treated.txt')
PSID = read.table('http://www.nber.org/~rdehejia/data/psid_controls.txt')
names(NSW) = c('treatment', 'age','education', 'black', 'hispanic',
'married', 'nodegree', 're74', 're75', 're78')
names(PSID) = names(NSW)
allData = rbind(NSW, PSID)
library(MatchIt)
Q = matchit(treatment ~ age + education + I(age^2) + I(education^2) +
black + hispanic + married + nodegree +
re74 + re75 + I(re74^2) + I(re75^2),
data = allData, method = "nearest",
distance = "logit", replace = TRUE )
Q