Because your image is in the Images folder beneath the root, it is correct to set the value of the key (in the web.config) as you proposed to "~/Images/bg_nav.gif". That part is fine but is completely independent of where you happen to put the handler (ASHX file). If, as you proposed, you put the handler in the root folder then the path to it from a CSS file in a subfolder of the root is, as your sample shows, ../PersistantImage.ashx. However, if your CSS file is in a SUBsubfolder (that is, two folders down in the hierarchy from the root) then the url for the background should refer to ../../PersistantImage.ashx in order to ascend two levels to reach the place where the handler is kept.
Remember, when you are stipulating the background's url to be the handler you have to provide a path to the PeristantImage. You can do so with a site-relative path (one that starts with a forward slash) or you can use a relative path. If you use a relative path then you have to remember that it is relative to where the CSS file lives. So you need to ascend as many levels up and then descend (if necessary) to wherever the handler lives.
You might also consider simply putting the handler in the same folder as your CSS file. Then you don't need a path in front of PersistantImage.ashx at all!!!
Good luck. Let me know if the flicker fix makes a difference for you.
Russ Helfand
Groovybits.com