That is a much funnier answer than I was expecting. 
That reminds me of a prank me and a couple friends pulled on my roommate in college. (he was also a friend, but… screw him any way!)
We superglue everything down in his room. Everything. Desk chair to the floor. Pencils and pens to the desk. TV remote to the table. Change to the nightstand. Left everything exactly the way it was… just glued down.
Evil:D
Thanks for all the suggestions. I do have surgical spirit in the house so will bring it in tomorrow and sort the shoes out.
I did complain that she didn’t rub the tape off my ass when she stuck me to my chair (it eventually came off in the laundry) and therefore I shouldn’t have to remove the tape from her shoes, but this didn’t wash with her.
This all began with me giving her some chilli sauce to eat which made her go purple (I did warn her it was extremely hot), then her hanging an inflatable shark over my desk and throwing about 50 stress balls at me while I was trying to work. I returned one of the balls, which hit her on the head quite hard, and she vowed eternal revenge.
Now I need to think two steps ahead for the inevitable retaliation. I might Duck Tape her phone receiver down, I think, or do that irritating thing with a second wireless mouse… Further suggestions gratefully received.
Give up now. Nothing you can do will ever stop the suffering that is your life from this point forward.
WD40 will work, as will some cooking oil (but that takes a little while.)
Ask her out already, you fool!
In a war of escalation the winner is the one who jumps to nuclear annihilation first.
Are the soles rubber/synthetic or leather? If leather DO NOT apply any solvents like WD 40. The WD-40 will soak into the leather and possibly into the shoe’s footbed which would be …bad. If leather use ice cubes pressed against the tape glue residue to harden the gum and scrape it off with a sharp blade once it is brittle.
If rubber/synthetic apply WD40 sparingly on the end of paper towel then use on the shoe sole. DO NOT spray it directly on the shoe sole. If it leaks off the sole and onto the side of the shoe and gets onto the leather it can permanently discolor it. So will mineral spirits and alcohol. Mineral spirtis can dissolve some adhesives used in dress shoe manufacturing so be careful.
Isopropyl alcohol leaves less of smell than WD-40 but it is a far inferior solvent for the glues used in tape vs WD-40.
Does she have thunder thighs?
If so you could buy her some corduroy pants to drown out the other sound 
Eucalyptus oil.
The man speaks a truth. And he should know, for “fool” is almost his last name.
From orbit, of course. Unless the OP wants to leave a bit of doubt.
Also available at your local mini-grocery will probably be lighter fluid, which will work. If you have a choice, get Ronson’s rather than Zippo fluid. The Zippo stuff is pretty stinky.
The previous poster has anticipated me. As I understand it, lighter fluid and Goo Gone both contain naphtha, which is what does the job. Naphtha - Wikipedia
However, BE VERY CAREFUL when you use it. Not only is it flammable, but it could ruin the shoe.
I should not be encouraging this sort of thing, but…
Go down to the local magic/illusion/joke shop, and see if they have really BIG plastic bugs. Tape one around her phone. I used to tape these suckers on the mouthpieces of phones, back when phones were placed mouthpiece side down on the cradles. My victim would pick up the phone automatically, start talking, and find him/herself glancing down at the mouthpiece, WITH A HUGE FREAKING ROACH right next to the mouth. Hilarity ensued, on my part at least. Usually panic and revulsion ensued on their parts. Also, giant fake roaches are great to sneak into someone’s lunch. Bonus points if they pitch their lunch into the trash. There are many interesting places that a giant roach can be positioned, and even if your victim KNOWS that you have done this before, nobody expects the Giant Roach again.
However, messing with someone’s lunch is bad form. Use the Giant Roach in the lunch only if she messes with your lunch first.
If you can get an art gum eraser it will scrub all residue off without leaving any marks.
Then humbly return her shoes to her. Remembering to insert a small garden slug in the toe of each one first.
She will find this hilarious, and thank you for brightening her day. I guarantee it.
x2
[Not entirely sure if you can get it over there, but if you can will work like a charm.]
Warning: may cause her feet to be attacked by random koalas.
Taping your arse? Inflatable sharks? Come on, she wants you.
It does indeed sound like a strange flirtation. I recommend leaving one of those notes on her desk saying