All of your EZI items disappear going to your second play through, so don't even worry about them on your first play. You can't get them all until you have most of the score pieces, so try to follow the guide for "Score Piece Collector" closely, because the only way to play the right score piece is to have them all and count from the top to get to the right number. If you have missed any score pieces, counting to the right one will be impossible.
EZI Cracker - Play Score Piece 2 for the Gentlemanly Pop in the square of Forte City.
EZI Certificate - Play Score Piece 5 with Wiseman Maracas in the Glissando Cliffs.
EZI Photo - Play Score Piece 20 with Lonely Pitch at Lake Reverb.
EZI Scarf - Play Score Piece 4 for Captive Congo on the Pirate Ship Dolce. (3F-NW Door)
EZI Egg - Play Score Piece 14 for Killer Bell Lyre in a hidden cave in the Sharp Mountains.
EZI String Phone - Play Score Piece 1 for Celebrity Marcato in Baroque Castle. (2F-East)
Smiling EZI - Play Score Piece 6 for Contrary Marimba outside Hotel Ensemble in Baroque City.
Cherry EZI - Play Score Piece 3 for Worrywort Horn by the fountain in Ritardando.
EZI Pajamas - Play Score Piece 11 for Shallow Sweet in Baroque Castle. (2F-West)
EZI Paddle - Play Score Piece 7 for Granny's Girl Quena in the upper room of Hotel Ensemble in Baroque City.
EZI Handkerchief - Play Score Piece 18 for Conceited Choir in Baroque City.
Elite EZI - Play Score Piece 21 for Solitary String (cat) in Tenuto.
EZI Pendant - Play Score Piece 27 Methodical Gospel in Ritardando.
Small EZI - Play Score Piece 29 for Precocious Flute by the cave in Agogo Village.
Swimming EZI - Play Score Piece 15 for Twilight JuJu in the Chorus Plains.
Laughing EZI - Play Score Piece 9 for Strolling Ghost Note in Hanon Hills.
EZI Pocketbook - Play Score Piece 13 for Tenacious Coronet in Cantabile Inn.
Weekly EZI - Play Score Piece 16 with Gentle Harp in Baroque City.
Rainbow EZI - All the way to the east of Elegy City, inside a small urn. It is in front of the steps that takes you to the dunes.
EZI Bun - Play Score Piece 28 for Glamorous Oboe in Elegy City.
Chapel EZI - Play Score Piece 13 for Desolate Saburo in the Noise Dunes.
Note: Huge thanks to Ray5555 and Kaens from our forums and Kiryn Silverwing for her guide on Gamefaqs. If you are stuck at any point, check that guide out here.