Well, Processing itself comes w/ a built-in old Java JDK 6!

However, the appropriate way is always to have a Java JRE already installed.
Java is an interpreted bytecode language which demands a virtual machine to run!

That is true for MS's .Net Framework huge VM package as well!
And any other scripted language like Python, Lua, etc.
And JavaScript demands a browser!  

When you build a P5 project into a binary executable,...

As stated above, a Java program doesn't compile into machine code and demands a VM to run!

... or if it has an out of date one,...

If you compile your Processing code using an old JDK like 32-bit version 6 or even 5,
pretty much is sure to run anywhere! 

Well my issue is that if I write software using P5 and want to distribute it to users, I don't want to include the P5 environment with it.
I am aware that Java/P5 requires a JRE due to it demanding a VM to run, but the error that P5 apps throw when one is not present is not really helpful to end-users (non-programmers/P5 users). I suppose I could just write an installer that includes a general JRE with it, but that has a global impact on a user's machine, which is not desirable.

Anyway, I was just wondering if the "compiled" binaries you get when you build a project can be tweaked to point to an included JRE.

Processing is compiled into pure Java! So the only requirement is
a JRE equal or gr8er than the JDK used to compile your code!

Most machines have at least a JRE available, properly installed! Otherwise, it's their loss! 

P.S.: If you use JDK 5 to compile your program, even a Win98 can run it!!!

Yes, it gets "compiled" into a POJO jar, but there is an executable generated that runs the jar file to make it friendlier for Windows end users. If they DON'T have the proper JRE available then it's not their loss; it's my loss since I've lost a user/customer/client. For example, I do Java development and I keep all of my JDK/JREs out of the Path environment variable.
I suppose the only workaround for this is to just generate my own exe that uses a local JRE to ensure things work smoothly (then I can tweak the JRE to give it more resources if I want). I was just wondering if P5 had something out of the box to support this.

AFAIK, most Macs and Linux distros and other Unixes come w/ at least Java JRE 6 installed!
Even though Windows comes w/ only M$ .Net Framework installed, there are so many Java apps around, chances are that a Win user ends up installing Java along w/o even noticing it! 

No, Processing has not something like that out of the box. But there are some softwares able to do such bundle for you. Right now, their names escape me, but they should be easy to search.

So the [probably] preferred solution for this is JWrapper. It seems like a young solution, but it looks like it does very nice packaging and code signing for Windows, OSX, and Linux. It can even include its own JRE and it goes as far as to compress it better than a typical zip would (at least that's what they claim). So after exporting your P5 sketch, you could take the jar file it generates and presumably pass it through this software and get yourself some nice distributables.

Being able to allow a user/customer/client to quickly and painlessly get your software running is key to having people use your software. I guess I should have been more clear in that my goal is to not just post some random code on the internet, but to release quality software that users may or may not pay for.

Jestermax, did you ever find a suitable solution for distributing your application? 

As said above, look for these programs packaging jars with a jre into a single executable, or, like Processing, as a folder with appropriate files (launch4j can be start).