Yes, they are assembled on the fly, but I thought if they wasn't stored as part of a whole cached page somewhere. Are you using JoomFish and if you do, do you have the "System - Jfrouter" plugin disabled?

No I don't use Joomfish and I have no "System - Jfrouter" plugin

Please, go to Manage 301 Redirects in JoomSEF control panel and make sure the URLs aren't present there.

I checked a few and they weren't in that list (291 links)

Any other suggestions?

Hello,
from the history of this post:

1. I think think that when you have edited the link, you have confirmed that the redirection should be created; (JoomSEF asks about that by default); so, most likely I would expect that it is stored in 301 redirections table (those in JoomSEF, not in .htaccess)

2. if you are really sure there is not 301 redirect in JoomSEF (please double and triple check) then the other options are:
a) cache - at any level - JoomSEF, Joomla
b) some redirection in .htaccess or web server level
c) the default Joomla router translating it (but that should not be the case, if you followed David's suggestion to try to disable it)
d) there exists such file structure on the disk

Those are probably all possible variants that could be causing similar behaviour.
You could do the following:
1. check the 301 redirects once again
2. clear JoomSEF cache
3. clear all Joomla caches
4. turn just JoomSEF of (disable in JoomSEF / Configuration) but leave Joomla SEO on
- let us know about result (if the URL is still reacheble)
5. turn Joomla SEO off
- let us know about result (if the URL is still reacheble)
6. if answer to 4 and 5 is yes, then there must be physical file or some .htaccess redirect