I was referring to %userprofile% as C:\Users\<user>, where <user> is your Windows user name. Sorry if that confused you.
So... check into C:\Users\<user>\AppData\Local\VirtualStore\Program Files (where <user> is your Windows user name) and see if there's a folder called 東方紅魔郷 in there. If there is, the replay folder is very likely there as well.
As I said, the AppData folder is normally hidden. To make it visible, click Start and type Folder Options, then hit Enter. Go to the second tab and click "Show hidden files, folders and volumes" or something similar (I'm using French Windows 7, so I have to give a translation from French to English). Afterwards, click OK.