Without a good gauge of size, it's difficult to say, but...
Here in the Midwest there's a indigenous wild plum known locally as sand plum in most of KS & NE. In Oklahoma, it's known as the Chickasaw Plum.
While generally they grow in thickets, they CAN be cultivated/pruned/spoiled into an actual tree, much like sumac and some other thicket forming shrubs. Sand plums have an amazing color skin which thru jack o'lantern orange when ripening to almost maraschino red, while the pulp stays a yellowish-orange color. Our fruit size ranges from a pie cherry at the small end to the circumference of a quail egg at the large side.
I have been told by some folks that similar fruits (likely
landrace cultivars of the same wild plum species) are found moving west into the Eastern Colorado Plains, presumably further as well. One friend actually kept records of the coloration, flavor, size, and farm directions (from Intersection X go 3 west, two north, 1/2 back east, then back south into the creek bed) because she found at least 4 different styles of wild plum growing within 15 miles of her farm.
I say all of that to make this point. It's entirely possible what you had was a cultivated specimen of a
local wild plum tree or bush.