Without knowing the exact error, it's hard to say what's going wrong. I'm not overly familiar with scipy, but I suspect if there was no solution to these problems due to an inconsistent system, you would get a meaningful error.
My best guess would be a memory issue. During Gaussian elimination, sparse matrices can undergo a large amount of fill-in, where zeros become non-zeros. For example, one non-zero along the top row could potentially result in all the zeros below it up to the diagonal being filled in (set to non-zero). Have you experimented with different node reorderings (permc_spec parameter)? The default should be a pretty good job, but given there are a few in-built options I think it would be silly not to try them out.
There's a very good description of how this works (with pictures!) here (though this is mathworks site, so any implementation will be different to scipy).
Alternatively, if you can accept a close-but-not-exact answer, there are plenty of iterative methods that can get an approximate answer in a fraction of the time and memory requirements. Without knowing more about the nature of the matrix, it's hard to say which would be best - but you can experiment with any of the functions under 'Iterative methods for linear equation systems' listed here.