Or, if Alice is only recognizing his type rather than him, personally, the strange eye may be some kind of weapon system.
I'm thinking that she recognizes him, though. Like someone else said, I bet she took him apart once, and Mr. Pate put him back together.
Why would she be so nervous if she's already beaten him before? Well, maybe she only beat him because she had a weapon available that she doesn't have now.
On the other hand, you'd think he'd show more recognition of her if she'd beaten him up in the past. So maybe she is simply recognizing his type.
On the gripping hand, if he were a recognizable type, wouldn't Sedna recognize him too? Argh, I wish Jeph would go back to 2 strips a week. So much uncertainty!