I like Harlan Ellison's definition (he was a pointy-headed snot, but, still, I'll try and see if I remember how this went):
If the story could only possibly be told with a science-fiction element in place, then it's science fiction. Otherwise, it's just another genre, with sci-fi trappings.
In other words, something like the old TV show "Quantum Leap" is true sci-fi, because the entire story hinges around Scott Bakula jumping all over the second half of the 20th century. There's no way to tell his story without that element. Hence, it is sci-fi. "Star Wars," OTOH, would have worked AS A STORY within any number of other settings besides space. The fact that it happens to take place in space doesn't make it sci-fi; it's just a story that happens to take place in space.
Now, that said, the key difference between sci-fi and fantasy is that sci-fi builds off of existing practical or theoretical science, whereas fantasy does not. It's that simple. "Harry Potter" is fantasy because JK Rowling invented a "make-believe" world hidden inside the "real" world, with its own rules and laws that have nothing to do with the laws of physics, chemistry, etc, in the "real" world. The key to fantasy is that you're free to create your own rules, but once you do you have to stick to them. Which is why, say, bubotuber pus consistently has damaging effects on bare skin and the dragons don't suddenly start talking and trying to make friends with the humans.
The elements that make "The Terminator" sci-fi, for example, are: intelligent machines, which a bazillion well-funded and accredited researchers have been working towards for decades (there's the practical/theoretical science requirement) and the concept of time travel (which is a little hazier, but satisfies the Harlan Ellison requirement. John Connor wouldn't exist if he hadn't sent Kyle Reese back to save Sarah, ta-da, instant paradox.). With regards to things like time travel, faster-than-light speed, telepathy, and so on, unfortunately, there's really not a cut-and-dry defining line between sci-fi and fantasy; it's more a question of tone. "Harry Potter" has time travel and telepathy too, but because these occur in a larger fantasy context, they're handled as fantasy concepts. Where time travel, etc show up in sci-fi, they're treated in a way I've heard described as "imaginary science," which basically means that there's no theoretical, much less experimental, data from which to extrapolate, the author is under the same obligation as the fantasy author, to decide how his or her version of FTL or matter transmission or whatever works, and then stick to it. If there are other compelling sci-fi elements in the story (see: "The Terminator") then it's sci-fi, not fantasy.
So basically, the definition of sci-fi as "things that could happen" isn't far off, but that depends pretty keenly on your personal definition of reality. If you believe in angels and zombies, a story involving angels and zombies could be presented as entirely believable sci-fi. In fact, there's been a recent trend you may have noticed towards presenting zombies as a sci-fi concept. But we're getting closer all the time to a viable matter transporter, a "thought helmet," and flying cars, and I'm sure, as long as we don't blow ourselves up first, somebody will eventually figure out how to traverse interstellar distances. We already have tricorders and cloning and the Dick Tracy video watch.
I don't know a thing about Lord Loss or Shadowmarch, and I'm too lazy to go and look them up on Wikipedia right now, but I will tell you that the reason bookstores, etc, lump sci-fi/fantasy into a single genre is because the lines do blur rather easily and they can't be bothered either. Walk into a Blockbuster and take note of the fact that every single sci-fi/fantasy title is shelved under "Action," including "Gattaca," which may be the slowest movie ever made. I don't have all the answers, but this subject is a particular pet peeve of mine, so I hope I helped.