There are actual SLI-approved power supplies, and yes- many of them are 500W or more to give the overage needed for driving two power-hungry videocards.
One thing about Crossfire though- at this point in time, it's only supported on special ATI mainboards. They use the ATI Xpress SLI chipset.
I'm unsure if/when or how well Crossfire will work with NForce or other mainboards, or if they will work at all.