Yes, Virtual Earth provides a reverse geocoding service in the platform API.

You can see this in our Interactive SDK, http://dev.live.com/virtualearth/sdk expand "Find Information (Basic)", then click on "Reverse Find"

MSDN Library for this, http://msdn.microsoft.com/en-us/library/cc469978.aspx

You'll have the parse the output if you just want city/state but that's pretty trivial.

Enjoy.