If you know of this trick already, please do inform me.
SHEIMI
First use the E4 glitch (First E4 room, go to door and surf)
Land back on solid ground just south.
Reset your step counter!
Now go 200 steps east from the bottom door
Then go 363 steps south (563 steps total)
Then go 722 steps east (1285 steps total)
THEN go 19 steps west (1304 steps total)
Use underground kit.
You should appear underground, so just resurface!
You'll now be on some glitchy land
GO NORTH A BIT UNTIL SONG CHANGES
Check you map key item and cancel out of it!
Everything should be fine now, just go straight north and you'll find Sheimi! FAINT IT.
GO SOUTH ALL THE WAY. You'll see what looks like a big hole in the water.
Use surf, you'll bump into something, it's the Sheimi sprite. Fish on it (Not sure if this is required)
Get off, then go all the way back up, Sheimi should be standing there.