Kaspersky was happy to tell me that it detected a virus that it can't do anything about and windows rebooted midscan. Spybot and AdAware couldn't get rid of this thing either. Ran in safemode, file deleted on reboot, file back again. Strangely, couldn't find the filename in the registry. Ran HijackThis and it showed 2 weird entries for qxwtawj.dll.
Solution, at least worked so far, is to boot into ubuntu, rename both files to .bak, not sure if qxwtawj is a virus or not and can't find anything on google so remained it instead of deleting. Booted into windows, no alerts from kaspersky and xaaykvjr has not reappeared.
In the registry, qxwtawj appears under winlogon in uiphazue and another location. I wasn't able to delete either entry even using regassassin and regseeker. Finally got rid of the winlogon entry by running ComboFix. You can get it here, here, or here.