I can run lots of performance tools on my server, but what is with problems that are only visible from the outside? Are there any tools that can help me with this?
Check out http://www.webpagetest.org/. You can run tests against your site from a remote server and it will tell you how long any page took to load and how long each component took to load.
The site uses multiple servers around the world so you will be able to check if you have speed differences due to location.
This is still in the VERY early stages but you can capture a video of the page load for viewing and visually comparing to other pages.
It's not an online tool strictly speaking, but take a look at Yahoo! YSlow. It's a Firefox addon that integrates with Firebug.
One tool that I use regularly is the domain report at DNSStuff.com It's tests are mostly related to DNS and the domain name itself, but it can identify a number of things at the low level which can dramatically impact performance higher up the stack. I recommend running a DNS testing tool like this in addition to higher level tests to have all the bases covered.