Japanese releases are hardly region free ever, seriously.
Your best bet is Ketsui's Asian version (if it ever gets an Asian release) which is very likely be region free, or at least include PAL (because of Australia basically).
Last time I checked XBLA games are region locked, but wouldn't Braid make its way to PAL regions if it hasn't yet?