Bijection between binary strings and pairs thereof Input: Either one or two strings consisting of '0's and '1's.  If there are 2, they are separated by a space. All strings are of length at least 1.
Output:

If a single input was given as input,  2 are output.
If 2 were input, 1 is output.

The output strings can be whatever you like, but if running your program with input A gives you B, then running it with B must give A (if inputting 111 11 gives 00000, then inputting 00000 must give 111 11).
That means if you pipe your program to itself, you should get back whatever you input.  If your program is called foo, you can test that like this:
&gt;echo 101 101|foo|foo
101 101

To prevent the use of brute force techniques, your code should be able to run with 1000 digit strings in under 10 seconds.  My Python solution for this takes less than 1 second on 10000 digit strings so this shouldn't be a problem.
Shortest code wins.
Python, 183

Bijection is cached on disk.

x=raw_input()
try:d=eval(open('d').read())
except:d={'':'','1 ':'1 '}
t='1 '*not' 'in x
if x not in d:
 while t in d:t+=`(id(t)/9)%2`
 d[t]=x;d[x]=t
 open(*'dw').write(`d`)
print d[x]


edit: Oops, looks like this isn't the first smartassed answer.  Mine's consistent between runs!