We need to see the query profiler output to tell for sure (you can get it by adding the --profile flag to query explain). Note that you can still manually kill a query being profiled, the profiler will still collect the partial timings.
Re: queries, Query1 and Query3 (which both don't terminate) are essentially equivalent. There's not difference between ?s :p/:q ?o and ?s :p [ :q ?o ]. But Query2 is not and is substantially simpler because 3 out of 5 OPTIONALs are simple triple patterns and not BGPs of two triple patterns. Query2 can also potentially return different results from 1 and 3 (depends on the data).
Please do the profiling and then we can tell where the problem is.