The CBSA only facilitates work permit applications concurrent with processing your entry into Canada. You cannot just go to the border and ask for a permit. If you want to reinstate your legal status you have to apply online or on paper and ask for reinstatement.
You can also leave Canada and re-enter at the US-Canada border. This has to be done as a new entry. You are required to go on the US side and make an application there. Only after you made an application to the US border officials, you are considered to be "outside Canada". If there is a turning point and you really don't want to torture yourself with US officials, turn around and tell them you are coming from the US and if they want you to prove it, point out that you don't need proof because you have a duty under the IRPA to report on entry. You basically voluntarily and intentionally surrender yourself to CBSA jurisdiction, which forces them to process you.
So basically, when you go to the border and make a work permit application on entry, your 90-day grace period is GONE, you are not eligible for reinstatement. If the issue comes up if/why you overstayed (which is a contravention of the IRPA if you don't get reinstated which you can't because you left Canada), you tell them you were waiting for LMIA.
If your paperwork is in order, they should be able to issue your new work permit and re-admit you.
