Thanks for sharing this. Been having this problem for quite some time and just like everyone else, I was very frustrated. Love Google Now and Bluetooth in my car...I drive a LOT. Couple of things: first, does everyone have an exchange account through your employer? I tried working with our IT department and they insisted it wasn't anything on their end. VZW said the same, however, when I deleted the exchange account (and all the subsequent security stuff) I couldn't reproduce the problem. Now, going without work emails on my GS4 is not an option. Just wondering.
Second, I further tested Rirruto's settings and have found that I was able to keep Google Now on and then messed with the Voice settings. Under "Ok Google" detection, I am able to have the "From Google Search app" checked and be able to successfully make calls. However, when I checked "From Any Screen", the Audio History is automatically turned on and there becomes the problem. For now, I am able to use Google Now and Bluetooth without issues. Hoping it keeps working...