Yes, you can have same paid app on two iPhones
I have a 3G iPhone with latest update (2.2) as of January 3, 2009. I've been buying some apps on my iPhone. However, my daughter, who has the other iPhone in our account, also wanted one of the apps I just bought. So I went to her computer and logged in my account at the iTunes Store. When I clicked on the app to purchase it, a message came up that said I've already purchased the app and would I want to download it for free. So I clicked yes and I got it free for the other iPhone. The same happened for other apps that I've purchased previously. However, there was one dictionary app that I had purchased on sale and it wouldn't let me download it for free. I had to pay for it again.
So there, you can purchase and download for your first iPhone on the computer it's synced to. Then go to another computer, which the second iPhone is synced to, and download it for free for your second iPhone, using your same iTunes Store account.