Note: Admittedly, I am challenging your assumption that these phrases mean the same thing. I do try to give an actual answer near the end... so your mileage may vary.
Well, I don't know how much help I can be since I still see these two things as meaning separate things:
I am not sure if I'm allowed to do this
I am not for sure if I'm allowed to do this
The usage and essential point are definitely the same, but I pull this difference between the two:
I don't know if I am allowed to do this
I am not confident I am allowed to do this
Since you can stick one in for the other and usually end up with a corresponding sentence that means virtually the same thing, I can understand the confusion.
Flipping things into the positive case makes it a bit easier to reveal:
I am sure
I am for sure
The first is a statement of quality of knowledge. The second is a statement of trustworthiness.
But, really, this is ungrammatical to me:
I’m really not for sure what I’d do without you.
This is pulled from your first linked example. The author is also waxing poetic; I wouldn't put too much faith in this usage. The other examples all work with how I see the difference between the sayings:
I don't know which religion I am / I am not confident which religion I am
I don't know when... / I am not confident when...
I don't know why I see this difference or if it holds any water. I suspect the source is the simple answer:
I am not sure / I am not for sure
The usage of "for sure" in other phrases again implies a subtle difference:
This is a sure thing
This is for sure
I wouldn't say "this is sure." If I heard someone say "this is a for sure thing" I would balk at it but parse it to mean "this thing is for sure."
So, to actually attempt answering your question, both phrases are used in Minnesota and Texas. I grew up in Minnesota and "sure" is used all over the place with the most common stereotype being, "Yeah, sure." If I asked someone, "Are you for sure?" they would understand the question to be "Can I be confident in you?" If I asked them "Are you sure?" they would understand the question to be, "Do you have any idea what you are talking about?"
Texas also uses "sure" but not nearly as often and I have not noticed (or admittedly thought about) them using "sure" and "for sure" as the same thing. In the event that they were I was probably attaching the meanings coming in from Minnesota.