There is a book on changing beliefs through NLP which I believe is called "Changing Beliefs through NLP." The author mentions the most basic beliefs are those of the environment. These beliefs are usually not chosen consciously, and are axiomatic. These beliefs are the toughest to touch, because we see them as facts, rather than as beliefs subject to reinterpretation.
I've used the Belief paraliminal today to improve my health by removing my belief that I literally fall appart in the winter. It was difficult, because this belief (while ultimately about myself) is about the environment I live in - too cold, too dry, too hostile for Kaidenian survival. Replacing it with the belief that I have the power to control my own health was somewhat difficult, but I combined the spoken instructions with the techniques I learned from New History Generator and Instant Personal Magnetism, along with a story I heard about Milton Erikson inserting himself into a client's memories. Basically, I watched the events happen that supported the new belief, and then I explained to the self it happened to the meaning of these events.
For a metaphorical exploration of the subject of beliefs creating reality, and our experiences creating our beliefs, I would strongly recommend seeing [/I]Dark City[I]. This movie also uses the Eriksonian technique of injecting a guide and teacher into past memories.
