#Haskell <s>757 705 700</s> 692

 import Data.List
 data R=L Char|A R R|T R R|E
 h=[' '..'~']
 k(']':s)a=(a,s)
 k('^':s)_=l(k[]s)
 k('-':c:s)(a:b)=k([a..c]++b)s
 k('\\':c:s)a=k s(c:a)
 k(c:s)a=k s(c:a)
 l(a,b)=(h\\a,b)
 i c E=L c
 i c r=A(L c)r
 o(a,b)=(foldr i E a,b)
 z 0 t=E
 z n t=A(z(n-1)t)(T t(z(n-1)t))
 d s n=m(fst$r s)[[]] where{m E a=a;m(L c)a=[b++[c]|b<-a,length b<n];m(A r s)x=nub$(m r x)++m s x;m(T r s)a=m s(m r(a));r s=w(e s E);w(u,'|':v)=(\(a,b)->(A u a,b))(r v);w x=x;e(')':xs)t=(t,xs);e s@('|':_)t=(t,s);e s@(c:_)t=g t$f(b s);e[]t=(t,[]);g t(u,v)=e v(T t u);f(t,'*':s)=(z n t,s);f(t,'+':s)=(T t(z n t),s);f(t,'?':s)=(A t E,s);f(t,s)=(t,s);b('(':s)=r s;b('\\':s:t)=(L s,t);b('.':s)=o(h,s);b('[':s)=o(k s[]);b(s:t)=(L s,t)}

output:

 ghci> d "a{3}" 4
 ["a{3}"]
 ghci> d ".*" 1
 [""," ","!","\"","#","$","%","&","'","(",")","*","+",",","-",".","/","0","1","2","3","4","5","6","7","8","9",":",";","<","=",">","?","@","A","B","C","D","E","F","G","H","I","J","K","L","M","N","O","P","Q","R","S","T","U","V","W","X","Y","Z","[","\\","]","^","_","`","a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","{","|","}","~"]
 ghci> d "w\\w+" 3
 ["ww","www"]
 ghci> d "[abx-z][^ -}][\\\\]" 3
 ["x~\\","y~\\","z~\\","b~\\","a~\\"]
 ghci> d "ab*a|c[de]*" 3
 ["aa","aba","c","ce","cd","cee","cde","ced","cdd"]
 ghci> d "(foo)+(bar)?!?" 6
 ["foo!","foobar","foo","foofoo"]
 ghci> d "(a+|b*c)d" 4
 ["ad","aad","aaad","cd","bcd","bbcd"]
 ghci> d "p+cg" 4
 ["pcg","ppcg"]
 ghci> d "a{3}" 4
 ["a{3}"]

Explanation: this one's a textbook regex implementation. R is the regex type, with constructors A (alternate), L (literal) and T (then). The usual 'Star' doesn't appear because I inline it as alternates during the parse (see 'z'). 'm' runs the simulation. The parser (start at 'r s=....') is just recursive descent; 'k' parses ranges. The function 'i' expands ranges into alternations.