Steven Frank (of Panic fame) was unsatisfied with iPhone's notes, so he decided to hack up a little iPhone optimized wiki called W2 to use instead. It actually runs server-side, so you'll need a web server with PHP. Once installed, however, it'll allow you cross-link, embed images, search, and even use Gruber's excellent Markdown syntax. And of course you should be able to access the wiki from other web browsers besides the iPhone.
If you've got access to a web server with PHP and want to give notes the boot, you may want to check out the W2 free download. Keep in mind that it "is a hack thrown together in just a few hours" with potential security problems, so you'll probably not want to keep your credit card numbers on there.