(Most recent example from my own life that springs to mind: "It seems incredibly improbable that any Turing machine of size 100 could encode a complete solution to the halting problem for all Turing machines of size up to almost 100... oh. Nevermind.")

That does (did?) seem improbable to me. I'd have expected n needed to be far larger than 100 before the overhead became negligible enough for 'almost n' to fit (ie. size 10,000 gives almost 10,000 would have seemed a lot more likely than size 100 gives almost 100). Do I need to update in the direction of optimal Turing machine code requiring very few bits?