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.