Python 3, 709 705 685 664 662 615615 569
With @ceilingcat's improvements. Accepts input from stdin.
from string import ascii_uppercase as a
from itertools import product as d
import I,re,string
n=rangea=string.ascii_uppercase
k=inputd=lambda x:I.product()
p=inputrange(5),repeat=x)
t=lambda x:x(input()+x).upper().replace('J','I')
s=[]s=''
for _ in t(k+aa):
if _ not in s and _ in a:s.append(_)s+=_
m=[s[i:i+5]for i in nrange(0,len(s),5)]
e={r[i]+r[j]:r[-~i%5]+r[-~j%5]for r in m for i,j in d(n(5),repeat=22)if i-j}
e.update({c[i]+c[j]:c[-~i%5]+c[-~j%5]for c in zip(*m)for i,j in d(n(5),repeat=22)if i-j})
e.update({m[q][r]+m[u][v]:m[q][v]+m[u][r]for q,r,u,v in d(n(5),repeat=44)if(q-u)*(r-v)})
print(''.join(e[a+(b if b else'X')]for a,b in re.findall(r'(.)(?:(?!\1)(.))?',''.join([_ for _ in t(p'')if _ in a]))))
Example:
mfukar@oxygen[/tmp]<>$ python playfair.py
Stack Overflow
The cat crept into the crypt, crapped, and crept out again.
SIRACARDFMVUICVSMORDZNAKECMZMFBCYNRDFMSVTVKBTMMY