I would suggest easing into your organization system to allow your staff to get used to it. you don’t want a system to be so time consuming to use that people ignore it.
Start with a project number, then add some other element like folder structure, or whatever.
Excel may work initially, or have some web based service to track projects like Basecamp or equivalent
It reminds of the question of job tickets for IT support. For a quick 1 sentence solution it seems silly to open a tocket and potentially add hours or days to the response time, whereas larger issues that may take a lot of time or outside service to fix need to be tracked in more detail. So the question is, how do you determine the scope of a problem (or project in your case) and who makes that decision?