I can add that when I've changed the properties of avastui.exe file to "Run always as Admin" then at computer startup the UAC popup requested permission for the file to run and then Avast would start properly with one process, the right memory size and a tray icon. Since this approval took place at every startup I was very frustrated. Removed Spyboy (although it wasn't resident) and tried again the whole remove (safe+avast util) and reinstall this time running the setup file "as admin" (this was suggested by avast support over an email) but this has not resolved the issue.
I have also found an interesting article about avast not showing for delaying the system startup:
http://www.brighthub.com/computing/smb-security/articles/89227.aspx but after quickly looking at the alerts there I figured this was not the solution for my problem.
Some one who solved a similar issue by uninstalling avast with Appremover and deleting some registry leftovers manually - tried that - didn't make any difference.
I don't know how much trash was created on my computer after all of those installs-uninstalls but since the Avast support team basically stopped replying to my questions via email - I've just removed everything, had to go back to a restore point and installed a different free Anti-Virus program (AVG). I guess I'll keep following this post and might try Avast again later on.
Great Day and thanks for trying to help.