OS X Mavericks system restore from external drive using Time Machine I have a 3TB Seagate USB external drive (MBR scheme), divided in 2 primary partitions: one of ~500 GB has been created and formatted on Windows using Paragon Partition Manager with HSF+. 

I did a full system backup using Time Machine to this partition (apparently, successfully - or so I thought). (Directly, not as an image.)

When I try to follow this tutorial: http://support.apple.com/kb/PH14185 , as soon as I press Command R, I get thrown into an Internet Recovery, which takes about an hour to complete. I might be wrong, but, according to some research I've done, this should be the behavior when I don't have a dedicated recovery partition? If so - I don't see the point in creating the full system backup if I cannot readily make use of it. 

After said hour passes, I am presented with the options that should have readily been available to begin with, and I am able to do a system restore from the Time Machine.

Said restore, though, ends after a while in (what should have been?) a boot screen: I get the spinning wheel but the Apple logo is switched for a "crossed O" as in, the "Access denined" symbol. 

How could I prevent the Internet Recovery to take place, go directly to perform a Time Machine recovery? Any suggestions about the second issue, might they be connected somehow?
Your problem is almost certainly related to partitioning on a Windows machine.
You can verify this by using Disk Utility to look at the Drive, in particular the Partition Map Scheme. This needs to be GUID Partition Table but is probably MBR.

You would need to repartition on OS X, but this will need you to erase all data.