FIXED!
When I first had this issue I tried everything under the sun to fix it, including disconnecting/reconnecting the battery, SIM card in/out, Airplane Mode etc. Nothing worked. I had been dealing with no service for at least a month.
Today I was using my iPhone on 5% battery and not long after that it died. When it turned back on after giving it some charge I HAD SERVICE AGAIN!
So there's my answer, disconnecting the battery doesn't fix it, but lettting it die on purpose and recharging it does.
I hope this fixes the problem for everyone and not just myself.