Perfect Memento claims Alice was a human that turns into a youkai. The narrator of Dolls in Pseudo Paradise (presumably the blonde girl) states that she lost her humanity and stopped being human.
Perfect Memento states that Alice looks like a doll. Dolls in Pseudo Paradise presumably refers to the honest men (which includes the blonde girl (the dolls)) in Gensokyo (Paradise).
Perfect Memento describes Alice's house as a Western House in the forest of magic. The honest men come to take shelter in what's specifically stated to be a western house in the forest of magic.
Hanging comes into play at least twice in Dolls in Pseudo Paradise (IE, hanged dolls, given that the dolls in "Dolls in Pseudo Paradise" represents the honest men). Hanged dolls are also a feature of some of Alice's spell cards and her lose portrait in the fighting games.
The Blonde Girl kills one of the honest men by nailing him to a tree, presumably through means of voodoo dolls, considering that the man was indoors when it happens. Meanwhile, Bohemian Archive in Japanese Red gives us THIS official artwork.
http://en.touhouwiki.net/wiki/File:BAiJRAlice1.JPGOddly enough, every time I bring this stuff up, I almost never get any replies or commentary about it. Maybe it's just not as interesting as my "Maribel became Yukari" statements or something.
There's a whole bunch of other "stretch" evidence too, like how the girl on the cover dresses almost exactly like Alice, or how the girl in Dolls in Pseudo Paradise wanted to go back to the days of thievery (and Alice hangs around with Marisa a lot). Or the tea time (Alice is shown to be serving tea in tons of works, although admittingly so is Sakuya, but the chances of Sakuya being involved are pretty nonexistant), or the fact that the honest men have a foreign Shanghai party (Alice in her spell cards always refers to many foreign countries of the outside world, to the point where Marisa points it out in Grimoire of Marisa). But those things could of course be coincidences.
As in regards to the whole "Shiki POSSIBLY created Alice" thing, well, canon or not, ZUN says we can ignore the PC-98 series. So ignore it I shall! ....that said, if I were forced to acknowledge it, I'll just say "Well, Dolls in Pseudo Paradise ended with the blonde girl EXITTING paradise, right? Maybe she was going to Makai."