Audio output and volume controls gone after updating to iOS 5.1
From the fact that the issue persists across multiple firmware updates, it's almost definitely a hardware or firmware issue.

My first guess would be some small amount of metallic debris in the dock connector. It's likely that connecting and disconnecting the usb connection forces the software to assume that there is nothing connected, until the next time the phone wakes, when it checks if it's connected to a passive audio-out adapter.

Some metallic debris in the dock connector could force the phone into thinking there is always a line-out adapter present.

Try cleaning the dock connector with compressed air or a soft brush, or look into it with  bright light to see if there are any bent pins.