I was looking to see if this question was answered and found this thread. I’m looking into cutting Linoleum, and a great source of unmounted and mounted linoleum is McClain’s. The description of their material is pretty straightforward, and explicitly states it has no PVCs: “linseed oil, rosin, wood flour and limestone pressed onto a jute backing.”
McClain’s is a great source, too, because they will cut blocks to your specifications, which is super helpful if you don’t have a table saw or similar cutting equipment.
You can get it mounted on MDF, which seems to be an acceptable laser material, too? I was thinking given how one carves mounted linoleum for printing, exercising scoring control on a mounted piece of linoleum to outline a design and then carving away the unused portion would be potential preferable to cutting unmounted linoleum and mounting it, as all the smaller portions of what you wanted in your design would remain in place in the mounted version.