FWIW, here's a visual of the lot.

This is old, from Google street view. The big white rectangle on the building is gone. The smaller signs underneath and to the right... I think are gone but may still be there. The sign to the left of the big white rectangle (and the old, torn half-sign to its left, which I think is just litter waiting to be removed) are the only hints that this is anything other than an open lot.
The guy from the towing company and his pal sat on the raised brick flower bed to the left of the entrance. They saw us get out of our cars. We saw them. They almost certainly heard us discuss the question of whether or not it was a private lot, because that's what we were discussing when we were standing right there. They would have heard us say that we couldn't tell. They chose not to enlighten us.
If they were there to catch people who knowingly park in their lot and go somewhere else, that moment was precisely the one at which they could have proved it by saying, "Actually, it's a private lot" and pointing out the sign. If we had said, "Oh well," and kept on going, then they'd have been in the clear, ethically speaking.