Gamespot reports this little tidbit back in 2004:

Heavenly Sword, the title that proved to be the glue that kept the team together through these tough times, is currently in development for next-generation consoles. "We still have no publisher, but [we've encountered] plenty of interest [in the title]," (Ninja Theory chief designer Tameem Antoniades) added. The action title uses in-house technology and has been in development since early 2003.

Hit the jump to dive deeper into the rabbit hole, and 422 uses of the word "exclusive", mostly by Joe Pesci.

...Kung Fu Chaos, a game published in 2003 by Microsoft Games Studios exclusively for the Xbox and released on time, on budget and to critical acclaim in 2003.Ninja Theory believes that the next-generation of games consoles offer an opportunity to elevate the games experience into one that can rival film and literature and was one of the first development studios to commit exclusively to next-generation consoles.

Their previous success and dealings with Microsoft and the repeated use of "next-gen consoles", plural, suggests that not only may Heavenly Sword have been in development on the 360 before Sony swooped in on it, but also that Ninja Theory isn't likely to stay exclusive to the PS3 in the future. 

Either way, their game and their company has certainly come quite a way since it's meager beginnings.