Cowgirl, I think you are using the term "paint" in the generic sense-- to refer to the color of the horse? The confusion is arising because there is a formal breed called a Paint which has limited bloodlines, and most people involved in the stock horse breeds don't call a horse a Paint unless they are referring to that specific breed-- but I know that the generic term "paint" IS still being used to refer to color only by some people as well.
Its true, the color patterns generically called "paint" or "pinto" can occur on just about any combination of breeds. The American Paint Horse registry however has specific bloodline requirments-- a Paint horse (notice the capital P) will not have other breeds besides Paint, Quarter Horse, or Thoroughbred in its pedigree.
There is also a Pinto registry which will register horses with these spotted patterns but with a much more wide variety of bloodlines. The Pinto horse Association still has a list of approved breeds and still requires both parents be registered to register a Pinto stallion, but they do allow mares and geldings with the accepted color to be registered Pintos even if they have unknown pedigrees.
Hope that helps!
Also , please post pics of your horses if possible!