I like the idea of coding projects, for NA and Support reference; and I understand the 'number shock' you're having. My easy suggestion would be simply to *not* reuse the project numbers.
When project 123 is done, let the number be retired. As the project numbers start to get out of hand, (i.e., when they start to seem unwieldy to you) go back to 001 or whatever lowest number you use.
Might help, might feel wierd, but that's how I'm thinking about doing it.