I had lot of problems as well. In my case problems are almost solved by switching from SoftwareSerial to AltSoftSerial. It seemed that on the Uno the standard software serial library was not working for me. After switching I started to get results back for the first time. (I also used level shifting and external power supply for 3.3V)
And by almost solved I mean - I still gotget, from time to time some, gibberish on the terminal. So even AltSoftSerial isn't a perfect solution. I was using the ESP-07 with a baud rate of 115200 bps data rate.