Histogram operation for improving visual object tracking
I don't think you have any choice other than to use the same number of bins for each observation.  Otherwise not only will you not be able to average the histograms, you will also not be able to compare them.

And you definitely need to change the histogram slowly, i. e.
$$h = (1 - \alpha)h + \alpha h_{obs}$$ where $h$ is your "moving average" histogram, $h_{obs}$ is the histogram of the current observation, and $\alpha$ is a small factor, whose value you will have to tune experimentally.

As far as different sizes of observations, the simplest thing to do is to impose a hard constraint saying that the size of the object cannot change too much from frame to frame.