Symbol rate (baudrate) estimation
perhaps your demodulator already knows the baud rate

Many wireless communication protocols set the symbol_time to some known integer multiple of the chip-time or carrier cycle time.
Since you are able to demodulate the signal, your demodulator must already know the chip-time or carrier cycle time.
Perhaps you can take that time information and multiply it by the "known integer" to get the symbol_time; then you "merely" need to do phase alignment.
Is there any way to pull that time information out of your demodulator?

FFT

The symbol rate is approximately equal to the bandwidth.
(I hear that the -10 dB bandwidth is 1.19 times the symbol rate for QPSK -- is that true for all signal constellations?)

If you have a high enough SNR, you can put your signal through a FFT, and estimate the bandwidth.
I think this works in almost any format you have handy --
the raw ("real") modulated signal, or the demodulated ("complex" I,Q) baseband signal, or I alone, or Q alone -- but I don't think it will work if you feed phase data from the "Update #2" plot above into the FFT.

It's usually pretty easy for a human to visually pick out the -3dB bandwidth on a graph.
Is there a Matlab function for estimating the -3dB bandwidth?

When you have pure white noise coming in -- the SNR is too bad -- the -3dB "bandwidth" clearly has nothing to do with any real baud rate, but depends entirely on the filters used in your demodulator.

autocorrelation

You can find the autocorrelation of a function using the Matlab autocorr() or xcorr() functions.

There are at least 3 ways of converting that autocorrelation to an estimate of the baud rate:


With approximately uncorrelated data bits, the autocorrelation at offset time of exactly 1 symbol_time or more are going to be approximately zero, and the normalized autocorrelation at short offset times from 0.0 to 1.0 bit time is approximately linear: 1-(time/symbol_time). Fit a straight line to those short offset times to get a good estimate of the autocorrelation at non-integer offset times, find offset time t_half that gives an estimated autocorrelation of about 1/2 along that fitted line, and your symbol time is about symbol_time ~= 2*t_half.
During burst transmissions, some transmitters make every 10th bit a start symbol. Your autocorrelation function, as always, has one peak at 0 offset time; skip past that first peak, and search for the positive time t_positive that gives the next biggest positive peak (with expected amplitude roughly 1/10) in the autocorrelation function, and your symbol time is about symbol_time ~= t_positive/10.
Some transmitters use a stop symbol precisely 9 bit-times after every start symbol, and give the stop symbol the negative amplitude of the start symbol. Search for the offset time t_negative that gives the biggest negative peak in the autocorrelation function (with expected amplitude roughly 1/10), and your symbol time is about symbol_time ~= t_negative/9.


autocorrelation approximation

Many other techniques use some quicker-to-calculate approximation of the autocorrelation function -- in particular, there's really no point computing the autocorrelation amplitude at offset times greater than 10 bit_times.

In particular, let's calculate the autocorrelation function at only one time offset H:
Delay the signal by some time H, and multiply the delayed signal by the original (non-delayed) signal, and use some perfect or leaky integrator get a long-term average.
(If your input signal is already clipped to the +1 -1 range, like most FM and PSK receivers, then that long-term average is already normalized.
Otherwise, normalize by the average of the square of the signal, so your long-term average is guaranteed to be in the range of -1 to +1).

Then tweak H to try to get that normalized long-term average to be exactly 1/2 -- make time offset H shorter if the normalized long-term average is less than 1/2; make H longer if the normalized long-term average is more than 1/2.

Then your symbol time is about symbol_time ~= 2*H.

other techniques

The wikibook "Clock and Data Recovery" sounds promising, although it is still a rough draft. Could you update it to tell what approach worked best for you?

I've been told that many receivers use a Costas loop
or some other relatively simple carrier recovery technique to detect the baud rate.

The communications handbook
mentions a "early-late gate synchronizer".
Could you use something like this?

details

Many wireless communication protocols add many "redundant" features to the signal in order to make it easier for the receiver to lock onto and decode the the signal in spite of noise -- start bit, stop bit, trellis modulation, error detection and correction bits, constant prelude and header bits, etc.

Perhaps your signal has one or more of these features that will make your job easier?