Blocks being cached, even though Block Cache is Disabled

Hi,
I'm having a problem with blocks being cached unexpectedly. I have "Normal" caching enabled. Block caching is Disabled.

Here's the situation. We're using drupal as our main informational/support site (www.mycompany.com), while we have a web application running in a subdomain (app.mycompany.com). When logged into the web application, there is a cookie set (LoggedIn=1) which is accessible from any subdomain (.mycompany.com). So far, so good.

Here's the problem: When you're logged in to the web application, I'd like to show different links at the top of the page (like Home + Logout) than when you're not logged in (Sign Up + Login), and I tried doing this a few ways (which have all failed so far).

Attempt 1: Created a single Block element with an inline IF statement checking for existence of the LoggedIn cookie. This doesn't work because the Block gets cached in one mode or the other and doesn't get re-evaluated on each page load.

Attempt 2: I created two blocks (one for each set of links), and set their visibility to "Show if the following PHP code returns TRUE" and wrote some logic to test for the cookie and return the correct value. Once again, this gets cached, and the user doesn't see the correct links if they're logged in.

Attempt 3: I created two regions in my page.tpl.php template. The template has an inline IF statement which checks for the LoggedIn cookie and shows the appropriate region. I placed one link block in each region, and once again, things seem to get cached and don't show up correctly.

Basically, can someone explain to me a way to force some PHP code to get evaluated on each page load, while Normal caching is enabled?

Thanks,
-=Leo