There are many topics about this problem.
In my case, my phone gets no SIM icon when the battery is low, but it used to get no SIM icon even when it was almost full (more than 70%).
Usually the problem appeared when I used data (skype call over mobile data (not wifi) was the best way to end up with no telephony functions). It's not happening regularly, but it has something to do with low battery, high cpu load - even opening conversation made it happen (maybe the phone is overheated, or the SIM contacts are overheated).
When the problem occured. I was not able to connect to gprs data immediately after that, I finished in no SIM icon loop. When I waited 5 minutes and let the phone connect to network automatically, everything was good.

What kind of paper do you use under the battery? And how big is that? Is it under the whole battery space or just where the SIM card is located?
I'd like to try some more solutions, cause I have no doubt that in my case it'll get worse (as it did before). Any help appreciated.