If I say "I have no more apples" do I have to have had some apples to begin with? Is there an instance where I could start with none and still say I had no more sensically?
To the first sentence, yes, and to the second, no. No context in which I have ever heard this type of statement has supported the possibility of there having been no apples to begin with.
The basic reason I would infer for this is that we never use more per se to mean more than nothing. Hence, more always implies that there was at least one apple at the beginning.
There are two usages of no more. You could be showing a full apple-barrel to a customer and telling him that you have no more apples [than what is in front of him], or you could be sold out for the day and be telling him that you have no more apples [than what you already sold].
Semantically, there is no reason why no more shouldn't mean no more than nothing ever; it's just that no one has ever used it that way, and if someone has never had an apple, and still has no apples, he would say I have no apples, not I have no more apples.
Simply put, general usage says "no more" implies there having been some apples at another point in time. If there never were any apples to begin with, one might instead say, "We don't have (sell) apples."