I found the smallest multibase 2-12 bitstring at ~5.6 quadrillion: 10100001011000101000110101011011011101111110100101011 (53 bits)
Prime in base 2: 5678228814363947
Prime in base 3: 7182373369076078560696363
Prime in base 4: 21551394938288350689430921610309
Prime in base 5: 2309293677550186597171330299375393881
Prime in base 6: 29906514580824071121844506525456400608319
Prime in base 7: 89923361635195477013169537997440980347877207
Prime in base 8: 92771144347686777516300137625571104334947582473
Prime in base 9: 42260965547715496390905094752471441113979492989269
Prime in base 10: 10100001011000101000110101011011011101111110100101011
Prime in base 11: 1432168478679934708683628145065883323888809796182285059
Prime in base 12: 131956356859807386250777405024493135451219537385261159117
Not prime in base 13 (8464796925606551530766977421873448346565029813972573631633 = 139277326203487467720073 * 60776561098245690157424928651883721)
Small verification app on Coliru.
A big thank you to everyone who participated in this thread back in the day. My background is mostly on the code side, so the math optimizations discussed here (particularly the popcount and alternating bitsum tests) sped up the search by quite a bit. In total, this took a few months of CPU time on a Haswell i7, using a custom C++ program searching ~2.5 billion ints/second.
Along the way, I recorded anything that is a p9 or greater (where pN = a bitstring that is prime in bases 2-N), finding ~1K p9s, ~100 p10s, and six additional p11s:
1100101010110011000100100100010001000010010100011 is a p11 (445740908840099) (49 bits)
11110101101011010111001111111100010010100001101001 is a p11 (1080501296244841) (50 bits)
1000111001001101100010000100001110010111000011110001 is a p11 (2503418396111089) (52 bits)
1001001001110101000010110111110110011110101000111101 is a p11 (2576502425774653) (52 bits)
1011000111110100101011010101111010111010101001010111 is a p11 (3130631020849751) (52 bits)
1111010101010100100100001000101000000101101011101001 is a p11 (4315896816360169) (52 bits)
Full source code on GitHub:
https://github.com/JimViebke/Prime-Bitstrings (currently an MSVC project, but it shouldn't be too hard to port elsewhere)