Mathematica, 186 chars

{a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]

Example:

In[1]:= {a,b}=Characters/@StringSplit@InputString[]&~Array~2;{Length@#,Grid/@#}&[ReplacePart[b,Except[$|##&@@Tuples@#,{_,_}]->"."]&/@Select[Tuples[Subsets/@Range/@Dimensions@b],b[[##]]&@@#==a&]]  
? abb aba
? ababb aabba babab abbaa

Out[1]= {5, {a . . b b, a b . b ., a b . . b, . . . . ., . . . . .}}
             a . . b a  . . . . .  . . . . .  . a b b .  a . b b .
             . . . . .  . . . . .  . . . . .  . a b a .  . . . . .
             . . . . .  a b . a .  a b . . a  . . . . .  a . b a .

Python 2 with Numpy, 342 chars

from numpy import*
from itertools import*
import sys
S=str.split
C=combinations
R=range
a,b=[mat(map(list,S(x)))for x in S(sys.stdin.read(),'\n\n')]
n,m=b.shape
o,p=a.shape
z=[]
for i in product(C(R(n),o),C(R(m),p)):
 i=ix_(*i);e=b[i]
 if all(a==e):f=copy(b);f[:]='.';f[i]=e;z+=[f]
print len(z)
for x in z:print'\n'.join(map(''.join,x))+'\n'

Output Example

5
a..bb
a..ba
.....
.....

ab.b.
.....
.....
ab.a.

ab..b
.....
.....
ab..a

.....
.abb.
.aba.
.....

.....
a.bb.
.....
a.ba.

Haskell, 364 chars

m=map
l=length
u=unlines
v=reverse
z=zip[0..]
q s=p(lines s)[]
e i a=[a!!j|j<-i]
main=g.w.q=<<getContents
g x=(print.l)x>>(putStr.u.m u)x
c 0=[[]];c n=let x=m(m(1+))$c(n-1)in x++m(0:)x
p(c:x) a|c==""=(v a,fst$p x[])|1<2=p x(c:a);p[]a=(v a,[])
w(a,b)=[m(\(p,r)->m(\(q,x)->if(elem p i&&elem q j)then(b!!p!!q)else '.')$z r)$z b|i<-c.l$b,j<-c.l$b!!0,a==(m(e j).e i)b]

Ungolfed Version, 716 chars

parse (c:x) a | c == "" = (reverse a, fst$parse x [])
              | otherwise = parse x (c:a)
parse [] a = (reverse a, [])
readMat s = parse (lines s) []

choose 0 = [[]]
choose n = let
  x = map (map (1+))$choose (n-1)
  in x ++ map (0:) x

select ix a = [a!!i | i<-ix]

for = flip map
make b (ix, jx) = 
  for (zip [0..] b) (\(i,r) ->
    for (zip [0..] r) (\(j,x) ->
      if elem i ix && elem j jx
      then b!!i!!j
      else '.'
    )
  )

main = do
  s <- getContents
  let (a, b) = readMat s
      (n, m) = (length b, length.head$ b)
  let ans = [make b (ix, jx) | ix <- choose n, jx <- choose n, 
              a == (map (select jx).select ix$ b)]
  print$ length ans
  putStrLn$unlines.map unlines$ ans

Ruby 448

class Array
alias t transpose
alias z size
alias e each
alias s select
end

def x
v=[]
while(w=gets.chop).size>0 do
v<<w.split('')
end
v
end

def w(i,j)(0...i).to_a.combination(i-j).to_a end

a=x
n=a.z
a=a.t
o=a.z
b=x
q=b.z
r=b[0].z
w=['.']
y=w*r
z=w*q
f=[]
w(q,n).e{|u|w(r,o).e{|v|
h=b.dup
u.e{|i|h[i]=y}
h=h.t
v.e{|j|h[j]=z}
h=h.t
f<<h if(h.s{|i|i!=y}.t.s{|i|i!=w*n})==a}}
p f.z
puts
f.e{|b|b.e{|i|k='';i.e{|j|(k<<' ')if k.size>0;k<<j}
puts k}
puts}