I got the exact same problem with Froyo and Gingerbread ROMs, can't remember if I had that issue with MIUI ROMs, but definitely with CyanogenMod ROMs.
Instead of rebooting the phone I suggest switching flight mode on/off it's faster than a full reboot
Haven't found any real solution yet and always thought I'm teh only one with that problem as I couldn't find any other person with that issue. Right now I'm testing different Radio/ROM combination and if that doesn't work I'll need to check if any app is causing the problem.
Any chance you are using Tasker
Google Nexus 4 (LG Mako / LG-E960)
• Recovery: Team Win Recovery Project 220.127.116.11
• Radio: 2.0.1700.98
• SPL: MAKOZ30d
• ROM: OmniROM
• Kernel: Hells Doctor