Well if you've tried those programs you'd probably have to redownload the thing anyway to get a clean copy, so I'd suggest that. I'd also ping Steam's support, since if this is a general issue they would've heard of similar cases before. Personally I've never experienced this error with my copy of Borderlands, though.
GPF's tend to me memory related... have you run Memtest or some Linpack tests to check the system is running perfectly smooth? Can't hurt anything while waiting for support to get back to ya, at least.