Matchstick Equations
Javascript, 1069 Bytes

I've tested it with quite a few test equations and it seems to work all of the time now...

function w(t){function B(c,f){d=(c.length&gt;f.length?f:c).split("");e=(c.length&gt;f.length?c:f).split("");longer=Math.max(d.length,e.length);if(0!==d.length&amp;&amp;0!==e.length){c=[];for(x in d)for(y in c[x]=[],e)c[x][y]=1&lt;y-x?-1:function(c,n){r=0;for(j in n)-1&lt;c.indexOf(n[j])&amp;&amp;r++;return c.length+n.length-2*r}(a[d[x]],a[e[y]]);return v=function(f,n){for(var h=f.length-2;0&lt;=h;h--)c[n.length-1][h]+=c[n.length-1][h+1];for(h=f.length-2;0&lt;=h;h--)for(var q=0;q&lt;n.length-1;q++)1&gt;=h-q&amp;&amp;(c[q][h]+=-1==c[q][h+1]?c[q+1][h+1]:Math.min(c[q+1][h+1],c[q][h+1]));return c[0][0]/2}(e,d)}return-1}a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];a["+"]=[8,0];a["-"]=[8];a["="]=[7,9];a[" "]=[];l=0;p=[];u=[];r=/^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;b=/(=.*=|[+=-]{2,}|^[+=-])/;if(!t.match(r))return-1;g=function(c,f,t){if(0===t&amp;&amp;f.match(r)&amp;&amp;eval(f.replace("=","==")))c.push(f);else for(var n in a)t&gt;=a[n].length&amp;&amp;" "!=n&amp;&amp;!(f+n).match(b)&amp;&amp;g(c,f+n,t-a[n].length)};g(p,"",function(c){m=0;for(var f in c)m+=a[c[f]].length;return m}(t.split("")));for(var z in p)k=B(t,p[z]),u[k]||(u[k]=[]),u[k].push(p[z]);for(var A in u)return[A,u[A]];return-1}


Well this is my first time ever submitting an answer, so I don't see myself winning. This is basically a brute force method to figure out all answers and then it grabs and returns the smallest ones in an array. with the first argument being the length and the second being an array with the outputs.

if the input is "1-2=9" the output is [1,["1+2=3","7-2=5"]]

and here is the uncompressed code:

function ms(s) {
a=[[1,2,3,4,5,6],[4,5],[2,3,5,6,8],[3,4,5,6,8],[1,4,5,8],[1,3,4,6,8],[1,2,3,4,6,8],[4,5,6],[1,2,3,4,5,6,8],[1,3,4,5,6,8]];
a["+"] = [8, 0];
a["-"] = [8];
a["="] = [7, 9];
a[" "] = [];
l = 0;
p = [];
u = [];
r = /^([1-9]\d*|0)([+-]([1-9]\d*|0))*=([1-9]\d*|0)([+-]([1-9]\d*|0))*$/;
b = /(=.*=|[+=-]{2,}|^[+=-])/;
if (!s.match(r)) return -1;
function f(g,h)
{
    d=(g.length&gt;h.length?h:g).split('');
    e=(g.length&gt;h.length?g:h).split('');
    longer=Math.max(d.length, e.length);
    if(0!==d.length&amp;&amp;0!==e.length)
    {
        g=[];
        for(x in d)
        {
            g[x]=[];
            for(y in e)
            {
                g[x][y]=(y-x&gt;1)?-1:function(g, h){r=0;for(j in h)if(g.indexOf(h[j])&gt;-1)r++;return g.length+h.length-2*r;}(a[d[x]],a[e[y]]);
            }
        }
        v=function(d,e)
        {
        for(var y=d.length-2;y&gt;=0;y--) g[e.length-1][y]+=g[e.length-1][y+1];
        for(var y=d.length-2;y&gt;=0;y--)
            for(var x=0;x&lt;e.length-1;x++)
                if(y-x&lt;=1)
                    g[x][y]+=g[x][y+1]==-1?g[x+1][y+1]:Math.min(g[x+1][y+1], g[x][y+1]);
        return g[0][0]/2}(e,d)
        return v
    }
    return -1;
}
g=function(n, s, i){if (i===0 &amp;&amp; s.match(r) &amp;&amp; eval(s.replace('=','=='))){n.push(s);return;}for (var c in a) if(i&gt;=a[c].length &amp;&amp; c!=" " &amp;&amp; !(s+c).match(b)) g(n, s+c, i-a[c].length);};
g(p, "", function(q){m=0;for(var t in q)m+=a[q[t]].length;return m}(s.split('')));
for (var i in p)
{
    k=f(s, p[i]);
    if (!u[k]) u[k] = [];
    u[k].push(p[i]);
}
for (var q in u) return [q, u[q]];
return -1;
}


Warning: Don't do equations like 950-250=750 it uses ~45 Matchsticks and because this code uses brute force it will cause javascript to hang.