Bonjour BenotH,
Etant passé par là, je devrais pouvoir t'apporter pas mal de réponses.
Tout d'abord, la lettre de mise à pied n'a rien de nécéssaire. Il faut savoir que ça peut occasionnellement etre demandé dans certains cas, mais au final, sache que tu peux toi même changer d'emploi comme bon te semble. C'est juste que les agents interpretent (à juste titre) un JP comme un projet sérieux à long terme (donc 5 changement d'employeur en 1 an peut paraitre bizzare).
1. Alors, moi (fin 2015), j'avais lancé une demande papier (car il me semble que ce n'était la seule façon de faire cette demande de changement d'employeur). Pour information, avec un JP, on peut rester sur le territoire sereinement jusqu'a la durée de la fin du permis émis, même en ayant perdu ton travail. Il faut bien comprendre qu'un permis de travail est une autorisation de travailler pour un employeur X, donc il peut te licencier à un moment, puis pour une raison Y, te ré-embaucher par la suite (toujours dans la période de validité de ton permis et au même conditions évidement). Ceci dit, au passage à la douane, ça peut toujours se compliquer selon l'humeur et l'interpretation du douanier...
Alors, oui, techniquement, tu pourrais avoir des problèmes, mais au final, il est important de rester serein car convaincu de son droit à travailler au Canada comme initialement émis. Moi personnellement, j'ai démissionné et j'ai passé les frontières 2 fois sans emploi comme toi. La première fois, je n'ai eu aucune question (vancouver), mais la deuxième (toronto), le douanier m'a demandé si je travaillais... Comme je ne voulais dire que la vérité et que je ne comprennais moyennement ce qu'il me disait, il a reformulé la question "are you here for work", et là, j'ai dit oui avec un grand sourire

Car oui, tu ne travailles peut-etre pas mais t'est là pour travailler (et changer d'employeur car le programme EIC t'y autorise).
Si tu ne veux pas prendre de chance, attends ton nouveau permis de travail.
2.Je ne pense pas que ça soit le bon délai car toi tu fais une demande de prorogation/modification de permis de travail (et non pas un nouveau permis au titre de l'EIC). A l'époque (mais je pense pas que ça ai changé), il fallait envoyer son dossier papier à Vegreville (Alberta).
Oui, oui et re-oui, il faut attendre le délai et donc le nouveau permis reçu dans sa boite au lettre avant de travailler, c'est du vécu !
Donc si t'a un employeur capable d'attendre quelques mois, je te recommande de prendre des vacances au québec et de profiter des activités d'hiver, y a de quoi faire
Aller, bon courage BenotH