I've read some threads about renaming domain with exchange server 2007 but I'm not sure if this issue is the same with our case, which is we need to rename our server 2003 x64 with exchange 2007 from server1.domain.com to server2.domain.com. Is this possible without uninstalling our exchange server?

No it isn't. Whilst technically you can rename the server, doing so will break Exchange. If the hardware needs to be the same, then you'll still need to build a temporary server, move everything across,rebuildthe old server with a new name, then move everything back.

Just completely uninstall Exchange, right? No need to re-format the whole box.