You could have trusted third party intermediaries. If someone pays through one of those, and you receive through one of those, then it could be made instant.

Another reason to have Bitcoin banks?