Just ran across simpleswitcher, which does exactly what it needs to do. It asks the available windows directly from Xorg, which happens to be a lot faster than i3-py / IPC.
Arch-users can try it without thinking with AUR.
Edit: Should test stuff a bit longer before telling about it.
What works is to get a list of open windows on the current workspace, when asking for open windows on all workspaces. Using it to find on which workspace an app is buried, does not work. simpleswitcher relies on some EWM-Hints that are as yet not implemented in i3, and they are according to Michael not trivial to implement.
EDIT2: Here is a fork that has support for i3. It works really well. Archers: The AUR you should install is simpleswitcher-dd-git
.
EDIT3: The Fork has been renamed to rofi. It is excellent!