Find a multiple of a given number whose decimal representation looks like binary
Python 2, efficient solution, 99

n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

Thanks Sp3000 for some golfing tips.
I challenge everybody else to post (in their own answers) how long it takes to get the result for input 72 or 99 :) If those are really fast, try something like 79992 next (still &lt;1 sec here).
Explanation:
I thought this wasn't necessary (since the code is fairly readable), but I got a request, so here it goes:
The first idea is that a binary-looking number is a sum of 1 or more different powers of 10. Therefore, we can try to add various powers of 10 in different ways until we get remainder 0.
If we do that naively, it's the same as generating all binary-looking numbers and testing them. But a lot of remainders will be the same. A better way is to record only the smallest number that gave a certain remainder, and successively add greater powers of 10 to numbers we recorded. That's what the program does.
d is a dictionary/map where keys are remainders and values are binary-looking numbers with that remainder. The initial n:0 is a special case: it's supposed to be 0:0 so we can start adding powers to it, but the algorithm stops when finding key 0, so I used n instead, which is guaranteed to have the same effect and not interfere with the other values.
Then we start adding powers of 10 (stored in k) to all existing numbers and recording the remainders. We add k to the remainder: (x+k)%n and to the number: d[x]+k, and record it only if it's a new remainder: d.setdefault(…), then go to the next power: k*=10 and repeat until we get key 0: while min(d)
At the end, d[0] gives the binary-looking number that has remainder 0 mod n, so we divide it by n to get the solution.
Note: the program can be made more efficient by avoiding large numbers (recording exponents rather than powers of 10, and calculating remainders of powers from previous values), but it's code golf, so...
In fact, here, I wrote a faster version:
n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n