The server access log will fill up with 200 OK responses because as far as the file handling part of Apache is concerned, the request for example.com/randomgarbage has been happily fulfilled by /index.php?page=randomgarbage. Whether that script was able to return content or not is irrelevant as far as the access logs go.
If there is no "real" content to return for the current request, the PHP script should return the correct 404 status using the PHP HEADER directive and then "include" the HTML code and error message text of the 404 page.
Use the Live HTTP Headers extension for Firefox to see that 404 status is being returned. The server logs are of no use in this situation. The server logs tell you only whether a request was able to be fulfilled by the filesystem, or not.
The same applies whenever you return 404, 410, 301, etc, in fact any non-200 response from within PHP. The server access log will show 200 OK for those as well. That's why I often write a separate detailed log from within PHP. See a post from last year where I detailed a PHP script that made separate logs for 301, 404 and 410 responses returned from within PHP, and started a new dated log file for each one each week. The 301 log also detailed the target URL of the redirect as well as what was originally requested.
A large number of sites fail to return 404 for garbage requests. Some return a completely blank page, others return the normal page template but without it being populated with any content. This is one reason why Google highlights soft 404 responses with such vigour.