How can I sync Windows Live Contacts with my Iphone?

Export your contacts from Windows Live as a .csv file and save it on your PC. Then import the file into Outlook and sync it with your iPhone through iTunes.

Overview of syncing iPhone or iPod touch with your computer
http://support.apple.com/kb/HT1386

I don't use Hotmail so I am not sure if this will work but, as you are using Vista, try using Windows Mail and Windows Contacts (rather than Windows Live Mail) on your PC as this will sync with your iPhone through iTunes. If you set up Windows Mail to access your Hotmail account account, it may upload the contacts as well (but that's the bit I am not sure about).

You are right that MobileMe does not work with Windows Live Mail and its associated contacts (yet).

iPhone User Guide
http://manuals.info.apple.com/enUS/iPhone_UserGuide.pdf

Page 14

Contacts
Sync contacts with applications such as Mac OS X Address Book, Yahoo! Address Book, and Google Contacts on a Mac, or with Yahoo! Address Book, Google Contacts, Windows Address Book (Outlook Express), Windows Vista Contacts, or Microsoft Outlook 2003 or 2007 on a PC. (On a Mac, you can sync contacts with multiple applications. On a PC, you can sync contacts with only one application at a time.)

It Syncs with Vista Contacts and Microsoft Outlook. Figure out how to "sync not import export" your information from Hotmail into the supported application and you can sync your iPhone with that supported application.

Use Hotmail contacts in Windows Live Mail

With Windows Live Mail, you can use one program to access multiple e‑mail accounts, including Hotmail, Gmail, Yahoo! and many others. If you sign in with your Hotmail account, your Hotmail contact list becomes the address book for all your e‑mail accounts in Mail.

To download and install Windows Live Mail, go to the Windows Live Mail website and follow the download instructions.

When the download finishes, the Windows Live installer opens.

In the installer, review the agreements and choose any additional settings or services that you want to install with Mail.

When the installation finishes, click the Start Mail link in the installer.

Sign in to Mail with your Hotmail e‑mail address and password.

Click Contacts to view your contacts.

Use Hotmail contacts in Microsoft Office Outlook

The easiest way to sync your Hotmail contacts (as well as your Hotmail inbox) with Microsoft Office Outlook is to use the Microsoft Office Outlook Connector. Outlook Connector connects your Windows Live Hotmail account to Microsoft Office Outlook 2007 or Outlook 2003 for free. Changes you make to your contacts in Outlook are automatically synchronized with your Windows Live Hotmail account.

Close Outlook if it is open.

To download Outlook Connector, go to the Microsoft Office Outlook Connector page, and then click Download.

You might need to validate your Microsoft Office software before you can download Outlook Connector; if so, click Continue to start the validation.

In the Setup Wizard, review the agreements and install the Outlook Connector.

Open Outlook.

When Outlook Connector prompts you, type your Hotmail e‑mail address, password, and the display name you want to appear in e‑mail messages that you send using Outlook Connector.

Click OK.

Close and reopen Outlook.

It may take a few minutes to synchronize your Hotmail Inbox and mail folders.

Click Contacts.

Under My Contacts, click Contacts in, and select your Hotmail address to view your Hotmail contacts.